Baekjoon11444: 피보나치 수 6

피보나치 수 6

1 초

256 MB

6900

3453

2837

53.498%

문제

피보나치 수는 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,007으로 나눈 나머지를 출력한다.

풀이

이전 백준 문제 행렬 제곱을 풀었다면 수월하게 풀이할 수 있다.

피보나치의 풀이 방법으로는 반복문, 재귀, 동적 계획법이 있었지만 매우 큰 n에 대한 피보나치 수열 n항은 분할정복으로 풀이한다.

점화식

피보나치 수열 n+1항과 n항에 대해 다음이 성립한다.

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

행렬화

항들을 열거하면 n항을 하나의 식으로 나타낼 수 있다

| F(n+1) | =  |1  1| | F(n)   |
|  F(n)  |    |1  0| | F(n-1) |


| F(n+1) | =  |1  1|n | F(1) |
|  F(n)  |    |1  0|  | F(0) |

F(n+1) = |1  1|n | 1 | 의 [0][0]항
         |1  0|  | 0 |

다시 말해 피보나치 n항은 (1 1 / 1 0) 행렬을 n-1번 거듭제곱한 값의 [0][0]항이 된다.

데이터 타입

수의 크기 1000000000000000000은 long이 가능한 최대값보다 작은 수이므로 long을 사용할 수 있다.

중간계산마다 1000000007로 나누어 준다.

행렬의 거듭제곱

이전 항의 메소드를 미리 호출한다

long[][] before = Fibo(N/2);

호출한 다음 이 배열끼리 행렬의 곱을 진행해 다시 임시 배열변수 tmp[][]에 담는다.

만약 N이 짝수라면 tmp를 그대로 리턴하지만 홀수라면 나누면서 사라진 1승만큼 더 곱해주어야 하기 때문에

tmp2[][]를 새로만들어 tmp와 배열 [[1,1],[1,0]]을 곱한 값으로 넣고 리턴해 누락된 1승을 채워준다.

1항의 조정

n항을 구하기 위해서 n-1번 행렬을 곱하기 때문에 1인 경우 0번을 곱한다.

이에 1을 입력했을 때 정답이 1이 나오도록 조정해주어야 한다

import java.util.Scanner;
public class Main {
    static long[][] arr = {{1,1},{1,0}};
    static long[][] Fibo(long N){
        if(N==0) {
            long[][] arr2= new long[2][2];
            arr2[0][0]=1;
            return arr2;
        }
        else if(N==1) {
            return arr;
        }
        long[][] before=Fibo(N/2);
        long[][] tmp = new long[2][2];
        for(int i=0;i<2;i++) {
            for(int j=0;j<2;j++) {
                for(int k=0;k<2;k++) {
                    tmp[i][j]+=before[i][k]*before[k][j]%1000000007;
                }
            }
        }
        if(N%2==0) {
            return tmp;
        }else {
            long[][] tmp2 = new long[2][2];
            for(int i=0;i<2;i++) {
                for(int j=0;j<2;j++) {
                    for(int k=0;k<2;k++) {
                        tmp2[i][j]+=tmp[i][k]*arr[k][j]%1000000007;
                    }
                }
            }
            return tmp2;
        }
    }
    public static void main(String[] args) {
        long n = new Scanner(System.in).nextLong();
        long[][] answer = Fibo(n-1);
        System.out.println(answer[0][0]%1000000007);
    }}