백준 11444 피보나치 수 6 JAVA 풀이 (행렬 거듭제곱, 분할정복, 시간복잡도)

🔗 문제 링크

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

---

📌 문제 개요

N번째 피보나치 수를 구하는 문제

하지만 N의 크기가 매우 크기 때문에 일반적인 DP(O(N)) 방식으로는 시간 초과가 발생합니다.

 

📌 접근 방법

이 문제는 피보나치를 행렬 형태로 변환하여 해결

 

기본 행렬:

|1 1|
|1 0|

 

이 행렬을 N번 곱하면 다음과 같은 결과가 나옵니다.

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

 

 

 

result[0][1] = F(N) 이 됩니다.

---

📌 핵심 아이디어

1. 행렬 거듭제곱

A^N을 빠르게 구하기 위해 분할 정복 사용

짝수: A^N = A^(N/2) × A^(N/2)
홀수: A^N = A^(N/2) × A^(N/2) × A

 

 

2. 행렬 곱셈

 

 “가로 × 세로” 방식으로 계산

result[0][0] = a00*b00 + a01*b10
result[0][1] = a00*b01 + a01*b11
result[1][0] = a10*b00 + a11*b10
result[1][1] = a10*b01 + a11*b11

---

📌 처리 흐름

입력 N
→ 기본 행렬 생성
→ pow(base, N)
→ result[0][1] 출력

 

---

📌 전체 코드

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

public class Main {
    static final long MOD = 1000000007L;

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

        // 피보나치 상자
        long[][] base = {
                {1, 1},
                {1, 0}
        };

        // 피보나치 상자를 N번 사용한 결과
        long[][] result = pow(base, N);

        // 그 결과에서 F(N)이 들어있는 칸을 출력
        System.out.println(result[0][1]);
    }

    // 상자를 빠르게 여러 번 사용하는 방법
    static long[][] pow(long[][] matrix, long exp) {
        // 1번이면 그냥 자기 자신
        if (exp == 1) {
            return matrix;
        }

        // 빠른 방식 (분할 정복) - A^8 = (A^4) × (A^4)
        long[][] half = pow(matrix, exp / 2);
        long[][] result = multiply(half, half);

        // 홀수 처리 - A^5 = A^2 × A^2 × A
        if(exp % 2 == 1){
            result = multiply(result, matrix);
        }

        return result;
    }

    // 상자 2개를 합쳐서 더 큰 상자 만드는 것
    static long[][] multiply(long[][] a, long[][] b){
        long[][] result = new long[2][2];
        // 규칙 : 가로줄 × 세로줄 해서 더한다
        // [1 1]   [1 1]   [2 1]
        // [1 0] x [1 0] = [1 1]
        result[0][0] = (a[0][0] * b[0][0] + a[0][1] * b[1][0]) % MOD;
        result[0][1] = (a[0][0] * b[0][1] + a[0][1] * b[1][1]) % MOD;
        result[1][0] = (a[1][0] * b[0][0] + a[1][1] * b[1][0]) % MOD;
        result[1][1] = (a[1][0] * b[0][1] + a[1][1] * b[1][1]) % MOD;

        return result;
    }
}

---

📄 정리

이 문제는 단순 피보나치가 아니라

행렬 거듭제곱 + 분할 정복 을 사용하는 문제입니다.

• 피보나치를 행렬로 표현
• 분할 정복으로 빠르게 계산
• 결과에서 F(N) 위치 추출
• 피보나치를 행렬로 바꿔서 O(log N)으로 계산하는 문제