[백준 2749] 피보나치 수 3

피보나치 수는 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

---

N의 입력값이 1,000,000,000,000,000,000으로 1부터 계속 해당 값을 곱하기에는 너무나 큰 수다.

이렇게 큰 값들을 계산 및 처리할 때 사용하는 알고리즘이 분할정복이다.

분할 정복은 큰 문제를 작은 문제로 쪼개어 계산 한 후 해당 값들을 더해 나가면서 결과를 구하는 방식이다.

 

일반적으로 1부터 1,000,000,000,000,000,000까지 구할 때 걸리는 시간을 1초에 1번이라고 가정하면 1,000,000,000,000,000,000초이고 해당 방법을 분할 정복을 이용하면 log2의 1,000,000,000,000,000,000초가 걸리게 된다. 대략 60초이며 2의 60승이 1,152,921,504,606,846,976이다.

하지만 재귀적으로 수행되는 탓에 메모리를 많이 잡아먹게 된다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static long[][] fibo = {{1, 1},{1, 0}};
    public static final int MOD = 1000000;

    public static void main(String[] args) throws Exception {
        long N = Long.parseLong(br.readLine());

        long[][] res = matPow(fibo, N);
        bw.write(Long.toString(res[1][0]));
        br.close();
        bw.flush();
        bw.close();
    }

    public static long[][] matPow(long[][] tmp, long exp) {
        if(exp == 1) {
            return tmp;
        } else if(exp == 0) {
            long[][] zero = {{0, 0},{0, 0}};
            return zero;
        }

        long[][] res = matPow(tmp, exp / 2);

        if(exp % 2 == 1) {
            return matMul(matMul(res, res), tmp);
        } else {
            return matMul(res, res);
        }
    }

    public static long[][] matMul(long[][] tmp1, long[][] tmp2) {
        long[][] res = new long[2][2];

        res[0][0] = ( (tmp1[0][0] * tmp2[0][0]) + (tmp1[0][1] * tmp2[1][0]) ) % MOD;
        res[0][1] = ( (tmp1[0][0] * tmp2[0][1]) + (tmp1[0][1] * tmp2[1][1]) ) % MOD;
        res[1][0] = ( (tmp1[1][0] * tmp2[0][0]) + (tmp1[1][1] * tmp2[1][0]) ) % MOD;
        res[1][1] = ( (tmp1[1][0] * tmp2[0][1]) + (tmp1[1][1] * tmp2[1][1]) ) % MOD;

        return res;
    }
}

여기서는 피보나치 수를 구하기 위해 행렬을 이용하였다.

피보나치 수의 정의를 행렬식으로 변환하면 

위와 같은 식을 얻을 수 있다.

결과적으로 0번째 항, 1번째 항만 있으면 원하는 피보나치 수를 빠르게 구할 수 있다.

100만 MOD연산을 하게 되어도 999999 * 999999의 값은 int의 값을 넘을 수 있으니 long으로 선언 한 후 각 계산 마다 MOD 100만을 해 주면 된다.