BOJ 2749 피보나치 수 3(C++)

피보나치 수 3 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	1126	329	259	37.700%

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 1,000,000으로 나눈 나머지를 출력한다.

예제 입력 

1000

예제 출력 

228875

힌트

출처

• 문제를 만든 사람: baekjoon

비슷한 문제

• 2747번. 피보나치 수
• 2748번. 피보나치 수 2
• 10826번. 피보나치 수 4
• 10870번. 피보나치 수 5

#include    <cstdio>
#pragma warning (disable : 4996)
#define div 1000000
 
int ST[66];
long long int PRE[66][3][3];
int top = 0;
long long int ANS[3][3];
 
int main()
{
    long long int n;
    scanf("%lld", &n);
 
    while (n != 1 && n != 0)
    {
        ST[++top] = n % 2;
        n /= 2;
    }
    ST[++top] = n % 2;
 
    PRE[1][1][1] = 1; PRE[1][1][2] = 1; PRE[1][2][1] = 1; PRE[1][2][2] = 0;
    for (int i = 2; i <= 60; ++i)
    {
        PRE[i][1][1] = (PRE[i - 1][1][1] * PRE[i - 1][1][1] + PRE[i - 1][1][2] * PRE[i - 1][2][1]) % div;
        PRE[i][1][2] = (PRE[i - 1][1][1] * PRE[i - 1][1][2] + PRE[i - 1][1][2] * PRE[i - 1][2][2]) % div;
        PRE[i][2][1] = (PRE[i - 1][2][1] * PRE[i - 1][1][1] + PRE[i - 1][2][2] * PRE[i - 1][2][1]) % div;
        PRE[i][2][2] = (PRE[i - 1][2][1] * PRE[i - 1][1][2] + PRE[i - 1][2][2] * PRE[i - 1][2][2]) % div;
    }
 
 
    ANS[1][1] = PRE[top][1][1];
    ANS[1][2] = PRE[top][1][2];
    ANS[2][1] = PRE[top][2][1];
    ANS[2][2] = PRE[top--][2][2];
 
    while (top > 0)
    {
        if (ST[top] == 1)
        {
            int tmp11, tmp12, tmp21, tmp22;
            tmp11 = (ANS[1][1] * PRE[top][1][1] + ANS[1][2] * PRE[top][2][1]) % div;
            tmp12 = (ANS[1][1] * PRE[top][1][2] + ANS[1][2] * PRE[top][2][2]) % div;
            tmp21 = (ANS[2][1] * PRE[top][1][1] + ANS[2][2] * PRE[top][2][1]) % div;
            tmp22 = (ANS[2][1] * PRE[top][1][2] + ANS[2][2] * PRE[top][2][2]) % div;
            ANS[1][1] = tmp11;
            ANS[1][2] = tmp12;
            ANS[2][1] = tmp21;
            ANS[2][2] = tmp22;
        }
        top--;
    }
    printf("%d", ANS[2][1]);
 
    return 0;
}

피보나치 수 구하는 방법은 대부분 알지만 이 문제는 입력되는 n값이 너무 크다.. 

10^18이므로 일반적인 방법으로는 절대 안된다는 것을 알 수 있다.. 

그렇다면 뭔가 패턴을 발견해볼까.. 하고 봤지만 이 저급한 수학실력으로 패턴을 발견하기는 어려웠고...

행렬로 풀게 되었다.

Fn+1 = Fn + Fn-1 이고 

행렬로 나타내면

Fn+1    =  1  1  Fn

Fn            1  0  Fn-1

이 된다. 

그렇다면 

Fn+1  =  1  1  x 1  1  x 1  1  x 1  1  x . . . 1(F1)

Fn          1  0    1  0     1  0    1  0         0(F0)

= 1 1^n 1

   1 0     0

이 된다. 

결국 1 1 

       1 0 

의 n승일 경우를 찾으면 되는데, 여기서 행렬을 n번 곱하면 엄청난 연산이 될 것이기 때문에 

수학을 이용한다. 

X^21 = X^16*X^4*X^1 이 된다. 

10의 18승의 경우 2의 60승정도로 표현 가능하므로 배열을 대략적으로 잡아서 

1승, 2승, 4승, 8승.... 을 저장해 둔 후에 

입력받은 n을 2의 배수로 나누어(이진수 나누는 법과 동일)  

곱하면 연산이 훨씬 줄어든다. 

코드가 길지 않으니 코드를 보면 더 이해하기 쉬울 것 같다... (뭔가 설명하기가 어렵다 ㅠㅠ)