[백준] 2749번 - 피보나치 수 3 [Java]

https://www.acmicpc.net/problem/2749

 

[백준] 2749번 - 피보나치 수 3 [Java]

[백준] 2749번 - 피보나치 수 3 [Java]

---

1.  아이디어

 

피보나치 수의 N이 매우 커진 문제로 거듭제곱의 분할 정복과 점화식의 행렬 변환으로 해결할 수 있다.

---

2. 문제풀이

 

피보나치 수열은 a(n) = a(n-1) + a(n-2)의 점화식을 갖는데 이를 다음과 같이 행렬의 거듭제곱으로 표현할 수 있다.

 

$\begin{pmatrix}a_{n}\\ a_{n-1}\end{pmatrix} =\begin{pmatrix}a_{n-1}+a_{n-2}\\ a_{n-1}\end{pmatrix} =\begin{pmatrix}1&1\\ 1&0\end{pmatrix} \begin{pmatrix}a_{n-1}\\ a_{n-2}\end{pmatrix}$

 

$\begin{pmatrix}a_{n}\\ a_{n-1}\end{pmatrix} =\begin{pmatrix}1&1\\ 1&0\end{pmatrix} \begin{pmatrix}a_{n-1}\\ a_{n-2}\end{pmatrix} =\begin{pmatrix}1&1\\ 1&0\end{pmatrix}^{2} \begin{pmatrix}a_{n-2}\\ a_{n-3}\end{pmatrix} =\begin{pmatrix}1&1\\ 1&0\end{pmatrix}^{3} \begin{pmatrix}a_{n-3}\\ a_{n-4}\end{pmatrix}$

 

$\begin{pmatrix}a_{n}\\ a_{n-1}\end{pmatrix} =\begin{pmatrix}1&1\\ 1&0\end{pmatrix}^{n-2} \begin{pmatrix}a_{2}\\ a_{1}\end{pmatrix}$

 

a1, a2는 모두 1이므로 저 행렬의 거듭제곱만 빠르게 구하면 해결할 수 있다.

 

거듭제곱은 선형적으로 구하기에는 시간이 너무 많이 걸리므로 절반씩 나누어 곱하는 분할정복으로 O(log N)으로 해결할 수 있다.

 

구현은 정답을 출력하는 solve 메서드를 호출하고 solve 메서드가 행렬의 거듭제곱을 반환하는 recur 메서드를 호출해서 정답을 반환하도록 했다. recur 메서드는 N이 1이면 기본 행렬을 반환하고 1이 아닐 경우 짝수면 N/2 거듭제곱인 두 행렬의 곱을, 홀수면 N/2와 N/2+1 거듭제곱인 두 행렬의 곱을 반환하도록 했다. 두 행렬의 곱은 mul 메서드에서 구현했다.

---

3. 코드

 

import java.io.*;

public class Main {

    private static final long[][] baseMatrix = {
            {1, 1},
            {1, 0}
    };

    private static final int MOD = 1_000_000;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        long N = Long.parseLong(br.readLine());

        int ans = solve(N);
        System.out.println(ans);
    }

    private static int solve(long N) {
        if (N <= 2) return 1;

        long[][] matrix = recur(N - 2);
        return (int) ((matrix[0][0] + matrix[0][1]) % MOD);
    }

    private static long[][] recur(long N) {
        if (N == 1) return baseMatrix;

        long[][] half = recur(N / 2);

        if (N % 2 == 0) return mul(half, half);
        else return mul(half, mul(half, baseMatrix));
    }

    private static long[][] mul(long[][] m1, long[][] m2) {
        return new long[][]{
                {(m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0]) % MOD, (m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1]) % MOD},
                {(m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0]) % MOD, (m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1]) % MOD}
        };
    }

}

---

4. 후기