백준 11444 피보나치 수 6 Java: 행렬 거듭제곱으로 O(log N)

백준 11444번을 풀 당시 기록에는 50분 타이머 중 46분 1초에 제출했다고 남아 있다. O(N)으로는 풀 수 없다는 데서 출발해, 피보나치 점화식을 2×2 행렬로 옮기고 분할 정복을 적용했다.

• 백준 11444번 피보나치 수 6

핵심은 다음 전이 행렬을 N번 직접 곱하지 않고 이진 거듭제곱으로 O(log N)에 계산하는 것이다.

피보나치 점화식을 행렬로 옮기기

피보나치 수열의 F(n+1) = F(n) + F(n-1)을 행렬로 쓰면 다음과 같다.

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

전이 행렬을 Q라고 하면 Qⁿ의 [0][1] 원소가 F(n)이 된다. n=0일 때 Q⁰은 단위 행렬이고 [0][1]은 0이므로 같은 코드로 경계값도 처리할 수 있다.

지수를 절반씩 줄이는 이유

지수 n을 이진수로 보면 필요한 제곱 행렬만 결과에 곱할 수 있다.

1. 결과 행렬을 단위 행렬로 시작한다.
2. 현재 지수의 마지막 비트가 1이면 결과에 밑 행렬을 곱한다.
3. 밑 행렬을 제곱하고 지수를 오른쪽으로 한 비트 이동한다.
4. 지수가 0이 될 때까지 반복한다.

반복 횟수는 지수의 비트 수와 같으므로 O(log N)이다. 행렬 크기는 2×2로 고정되어 있다.

Java 코드

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

public class Main {
    private static final long MOD = 1_000_000_007L;

    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in)
        );
        long n = Long.parseLong(reader.readLine());

        long[][] transition = {
                {1, 1},
                {1, 0}
        };
        long[][] result = power(transition, n);
        System.out.println(result[0][1]);
    }

    private static long[][] power(long[][] base, long exponent) {
        long[][] result = {
                {1, 0},
                {0, 1}
        };

        while (exponent > 0) {
            if ((exponent & 1L) == 1L) {
                result = multiply(result, base);
            }
            base = multiply(base, base);
            exponent >>= 1;
        }

        return result;
    }

    private static long[][] multiply(long[][] left, long[][] right) {
        long[][] product = new long[2][2];

        for (int row = 0; row < 2; row++) {
            for (int col = 0; col < 2; col++) {
                for (int mid = 0; mid < 2; mid++) {
                    product[row][col] = (
                            product[row][col]
                            + left[row][mid] * right[mid][col]
                    ) % MOD;
                }
            }
        }

        return product;
    }
}

곱셈에는 long을 사용한다. 두 원소를 곱하는 순간 int 범위를 넘을 수 있기 때문이다. 각 덧셈 뒤에도 나머지를 취해 중간값이 불필요하게 커지지 않도록 했다. 밑 행렬을 전역 상태로 바꾸지 않고 지역 변수로 유지하면 함수를 다시 호출할 때도 결과가 서로 영향을 주지 않는다.

우연히 맞힌 것이 아니라 연결해 낸 것

당시 글에는 “그냥 점화식을 행렬로 만들어 볼까 했는데 이게 됐다”는 놀라움과, 우연으로 푼 것 같다는 의심이 함께 적혀 있다. 하지만 큰 입력을 보고 O(log N)을 떠올리고, 이미 배운 행렬 거듭제곱과 점화식을 연결한 과정 자체가 풀이의 핵심이다.

이 문제는 백준 10830 행렬 제곱의 행렬 곱셈과 백준 1629 곱셈의 이진 거듭제곱을 합친 형태로 볼 수 있다.

검증 범위

Java source를 수동 검토했다. n=0, n=1, 작은 연속 구간과 큰 지수의 모듈러 결과를 반복문으로 만든 피보나치 수와 대조한다. 현재 환경에는 실제 JDK가 없어 compile·judge 재제출은 live 반영 전에 별도 확인이 필요하다.