[C/C++] 백준 #1788 피보나치 수의 확장(수열)

피보나치 수열은 보통 0 이상의 항에 대해서 다루고 있습니다.

 

$$F(0)=0,F(1)=1$$

$$F(n)=F(n-1)+F(n-2)$$

 

형태의 점화식을 사용합니다.  음수항의 경우에도 그대로 적용될 수 있습니다.  $F(-1)$ 값은 $F(-1)+F(0)=F(1)$을 만족해야 하기 때문에 1의 값을 가집니다.  마찬가지로 $F(-2)$ 값은 -1의 값을 가집니다.  0 이상의 항이 0 이상의 값을 항상 가지는데 비해, 음수항들은 음수값을 가지는 경우가 발생합니다.

 

fibonacci projections

 

사실 피보나치 수의 경우 일반적으로 푸는 방식은 차례대로 풀어나가는 것입니다.  최대항의 절대값이 백만정도이므로, 순차적으로 계산해도 크게 문제가 되지 않습니다.  알고리즘 효율은 $O(N)$이기 때문이죠.  그래서 전 그것을 그대로 이용했습니다.  항의 절대값이 크다면, 행렬을 사용하는 방법을 생각해야 합니다.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//--------------------------------------------------------------------
//    baekjoon #1788 - Expansion of Fibonacci Series
//        - by Aubrey Choi
//        - created at 2019-07-06
//--------------------------------------------------------------------
#include <stdio.h>
#define    MOD    1000000000
int main()
{
    int f[2] = {0, 1}, n, ans, i;
    scanf("%d", &n);
    if(n >= 0)
    {
        for(i=1;i<=n/2; i++)
        {
            f[0]=(f[0]+f[1])%MOD;
            f[1]=(f[0]+f[1])%MOD;
        }
        ans=f[n&1];
    }
    else
    {
        for(i=0,n=-n-1;i<=n/2;i++)
        {
            f[1]=(f[1]-f[0])%MOD;
            f[0]=(f[0]-f[1])%MOD;
        }
        ans=f[(n+1)&1];
    }
    printf("%d\n%d\n", ans>0?1:ans<0?-1:0, ans>0?ans:-ans);
}