Level 2. 피보나치 수

Level 2. 피보나치 수

 

 

문제 설명이 조금 이상하지 않나 싶다..

 

설명만 보면 피보나치 수열을 모두 구한 후에 1234567로 나눈 나머지를 구하는 건 줄 알았는데, 질문하기 페이지를 보니 매번 F(i)를 1234567로 나눈 나머지를 구해야 하는 것이었다.

 

F(n) = F(n - 2) % m + F(n - 1) % m = {F(n - 2) + F(n - 1)} % m을 활용해 해결했다.

 

피보나치 수열을 구할 때는 전전 숫자와 전 숫자만 알고 있으면 되기 때문에, 굳이 배열을 사용하지 않아도 된다.

 

#include <iostream>

using namespace std;

int solution(int n)
{
    int pp = 0, p = 1, c = 1;

    while (0 < --n)
    {
        c = (pp + p) % 1234567;
        pp = p;
        p = c;
    }

    return c;
}