[BOJ/Java] 2749. 피보나치 수 3

[BOJ/Java] 2749. 피보나치 수 3

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

---

문제 해석

피보나치 수 3 문제는 \(n\)번째 피보나치 수를 \(1,000,000\)으로 나눈 나머지를 구하는 문제이다. 단, \(n\)은 \(1,000,000,000,000,000,000\)까지 가능하므로, 일반적인 재귀나 반복문으로는 해결할 수 없다. 이 문제는 **피사노 주기(Pisano Period)**를 활용하여 해결할 수 있다.

풀이 과정

1. 피사노 주기 이해: 피보나치 수를 \(m\)으로 나눈 나머지는 주기를 가진다. 이 주기를 피사노 주기라고 하며, \(m = 1,000,000\)일 때 피사노 주기는 \(1,500,000\)이다.
2. 피사노 주기 활용: \(n\)을 피사노 주기로 나눈 나머지를 계산하여, \(n\)을 \(1,500,000\) 이하의 수로 줄인다.
3. 피보나치 수 계산: 줄어든 \(n\)에 대해 피보나치 수를 반복문으로 계산한다.
4. 결과 출력: 계산된 피보나치 수를 \(1,000,000\)으로 나눈 나머지를 출력한다.

코드

import java.io.*;
import java.util.*;

public class Main {
    static final int MOD = 1_000_000;
    static final int PISANO_PERIOD = 1_500_000; // 피사노 주기

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

        // n을 피사노 주기로 나눈 나머지 계산
        n %= PISANO_PERIOD;

        // 피보나치 수 계산
        long[] fib = new long[PISANO_PERIOD + 1];
        fib[0] = 0;
        fib[1] = 1;
        for (int i = 2; i <= n; i++) {
            fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;
        }

        // 결과 출력
        System.out.println(fib[(int) n]);
    }
}

시간 복잡도 분석

시간 복잡도는 \(O(\text{PISANO\_PERIOD})\)이다. 피사노 주기는 \(1,500,000\)이므로, 이 범위 내에서 피보나치 수를 계산하는 데 선형 시간이 소요된다. 이는 문제의 제약 조건 내에서 효율적으로 동작한다.

느낀점

이 문제는 피사노 주기를 활용하여 큰 \(n\)에 대한 피보나치 수를 효율적으로 계산하는 방법을 배울 수 있는 좋은 문제이다. 특히, 수학적 지식을 활용하여 문제를 해결하는 과정에서 수학과 알고리즘의 조화를 느낄 수 있었다. 이러한 문제는 암호학이나 수학적 최적화에서 활용될 수 있을 것 같다.