[백준] BOJ_11444 피보나치 수 6

1. 문제 정보

• 문제 요약: 번째 피보나치 수를 로 나눈 나머지를 구하시오.
• 핵심 제약 조건: 은 보다 작거나 같은 자연수입니다.
• 난이도: Gold II
• 링크: https://www.acmicpc.net/problem/11444

---

2. 접근 방식

이 문제는 전형적인 Dynamic Programming(DP)이나 반복문으로는 절대 해결할 수 없습니다. 시간 제한은 통상적으로 1초(약 1억 번의 연산)인데, $N=10^{18}$이라면 $O(N)$ 알고리즘으로도 수천 년이 걸리기 때문입니다.

우리는 $O(\log N)$의 시간 복잡도를 가진 알고리즘이 필요합니다. 여기서 행렬 거듭제곱(Matrix Exponentiation) 아이디어가 등장합니다.

2-1. 문제의 본질

피보나치 수열의 점화식은 선형적입니다.

$F_{n} = F_{n-1} + F_{n-2}$

이 선형 관계식을 행렬로 표현하면, 다음 상태를 현재 상태의 행렬 곱으로 나타낼 수 있습니다. 이를 통해 $N$번의 덧셈을 행렬의 $N$승 문제로 치환하는 것이 이 문제의 핵심입니다.

2-2. 알고리즘 설계 (Design)

피보나치 수열을 행렬식으로 유도하는 과정은 다음과 같습니다.

$\begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix}$

위 식을 계속 전개하면 다음과 같은 일반항을 얻을 수 있습니다.

$\begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n$

즉, 기본 행렬 $A = \begin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix}$를 $N$번 거듭제곱하면, 결과 행렬의 $(0, 1)$ 혹은 $(1, 0)$ 위치에 우리가 원하는 $F_n$ 값이 존재하게 됩니다.

2-3. 분할 정복을 이용한 거듭제곱

단순히 행렬을 번 곱하면 여전히 $O(N)$입니다. 하지만 분할 정복(Divide and Conquer)을 이용하면 연산 횟수를 획기적으로 줄일 수 있습니다.

• $N$이 짝수일 때: $A^N = A^{N/2} \times A^{N/2}$
• $N$이 홀수일 때: $A^N = A^{N/2} \times A^{N/2} \times A^1$

이 로직을 사용하면 $10^{18}$번의 연산을 약 60회($\log_2 10^{18} \approx 60$)의 행렬 곱셈으로 줄일 수 있습니다.

---

3. 코드 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static long N;
    static final long MOD = 1_000_000_007;

    public static void main(String[] args) throws IOException {
        N = Long.parseLong(br.readLine());
        // 초기 행렬 {{1, 1}, {1, 0}}을 N번 거듭제곱
        long[][] answer = recursion(new long[][]{{1, 1}, {1, 0}}, N);
        
        // 결과 행렬의 [0][1] 위치가 Fn에 해당함
        System.out.println(answer[0][1]);
    }

    // 분할 정복을 이용한 행렬 거듭제곱 함수
    private static long[][] recursion(long[][] result, long n) {
        if (n == 1)
            return result;

        // 지수를 절반으로 나누어 재귀 호출
        long[][] tmp = recursion(result, n / 2);
        
        // 반환된 행렬을 제곱 (tmp * tmp)
        tmp = calculate(tmp, tmp);

        // 지수가 홀수라면 초기 행렬을 한 번 더 곱해줌
        if (n % 2 == 1)
            return calculate(tmp, result);

        return tmp;
    }

    // 2x2 행렬 곱셈 함수
    private static long[][] calculate(long[][] a, long[][] b) {
        long[][] result = 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++) {
                    result[i][j] += a[i][k] * b[k][j];
                    result[i][j] %= MOD; // 모듈러 연산 필수
                }
            }
        }

        return result;
    }
}

---

4. 회고 및 배운 점

시간 복잡도 분석: $O(N)$ vs $O(\log N)$

일반적인 DP 방식(메모이제이션)은 $N$ 크기만큼의 배열을 채워야 하므로 $O(N)$의 시간 복잡도를 가집니다. $N=10^{18}$일 때 이는 절대 불가능합니다.

반면, 행렬 거듭제곱 방식은 지수를 절반씩 줄여나가므로 $O(\log N)$의 복잡도를 가집니다. $2 \times 2$ 행렬의 곱셈 연산은 상수 시간(8번의 곱셈과 4번의 덧셈)이 소요되므로 무시할 수 있습니다.

구현 디테일

• Base Case: if (n == 1) 조건을 통해 재귀의 종료 시점을 명확히 했습니다.
• 홀수 처리: n % 2 == 1일 때 기본 행렬(result)을 한 번 더 곱해줌으로써 지수 법칙($A^n = A^{n-1} \times A$)을 완벽하게 구현했습니다.
• 결과 값 위치: 위에서 유도한 식에 따라 $A^N$의 결과 행렬에서 $F_n$은 1행 2열(answer[0][1]) 혹은 2행 1열(answer[1][0])에 위치합니다. 코드에서는 answer[0][1]을 출력하여 정답을 맞췄습니다.