[BaekJoon] 2749 피보나치 수 3 (Java)

1.  문제 링크

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

2.  문제

요약

• 피보나치 수는 0과 1로 시작하고, 0번째 피보나치 수는 0, 1번째 피보나치 수는 1입니다.
• 2번째부터는 바로 앞 두 피보나치 수의 합이 됩니다.
• 이를 식으로 써보면 $F_n = F_{n - 1} + F_{n - 2}$ (n ≥ 2)가 됩니다.
• n이 주어졌을 때, n번째 피보나치 수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1,000,000,000,000,000,000보다 작거나 같은 자연수인 n이 주어집니다.
• 출력: 첫 번째 줄에 n번째 피보나치 수를 1,000,000으로 나눈 나머지를 출력합니다.

3.  소스코드

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

public class Main {
    static final int DIVIDE = 1000000;
    static long n;
    static void input() {
        Reader scanner = new Reader();
        n = scanner.nextLong();
    }

    static void solution() {
        int pisano = DIVIDE / 10 * 15, objectiveIdx = (int)(n % pisano);
        int[] fibo = new int[pisano + 1];

        fibo[0] = 0;
        fibo[1] = 1;

        for(int idx = 2; idx <= pisano; idx++) {
            fibo[idx] = (fibo[idx - 1] % DIVIDE + fibo[idx - 2] % DIVIDE) % DIVIDE;
        }

        System.out.println(fibo[objectiveIdx]);
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;
        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }
}

4.  접근

피사노 주기

• IBM 직원 Donald Wall은 피보나치 수를 어떤 수 K로 나눈 나머지가 주기를 이룬다는 것을 증명하였습니다.
• 주기의 길이를 P라고 하면, N번째 피보나치 수를 M으로 나눈 나머지인 (N % M)은 (N % P)번째 피보나치 수를 M으로 나눈 나머지인 ((N % P) % M)과 같습니다.
• 여기서 주기는, M = $10^k$(k > 2)일 때, 항상 15 × $10^{k - 1}$입니다.
  
  
• n의 크기가 최대 1,000,000,000,000,000,000이기 때문에 피보나치 수를 구하는 것은 시간이 초과됩니다.
• 그렇기 때문에 피사노 주기를 이용하여 해결합니다.
  • 1,000,000($10^6$)으로 나눈 나머지를 구하는 것이기 때문에 피사노 주기에 따라 주기는 (1,000,000($10^6$) / 10) × 15인 $10^5$ × 15가 됩니다.
  • 우리가 구하려고 하는 수를 생각해봤을 때, 0번째 피보나치 수부터 1,000,000,000,000,000,000번째 피보나치 수까지를 1,000,000으로 나눈 나머지들을 모두 알게 된다면 어떤 n이 주어지더라도 답을 구할 수 있습니다.
  • 그런데 피사노 주기에 따라 N % 1,000,000의 값이 ((N % ($10^5$ × 15(주기))) % 1,000,000)과 같고 그 주기는 위에서 구한 바와 같이 $10^5$ × 15이므로 0, 1번째 피보나치 수는 0, 1로 정해져있으니 2번째 피보나치 수부터 $10^5$ × 15번째 피보나치 수까지 1,000,000으로 나눈 나머지를 구해놓으면 어떤 n이 들어오더라도 답을 구할 수 있습니다.
  • 우선 $10^5$ × 15번째 피보나치 수까지 1,000,000으로 나눈 나머지를 구해놓고 입력된 n을 ($10^5$ × 15)으로 나눈 나머지를 구합니다(이 수를 편의상 x라고 하겠습니다).
  • 우리는 위에서 구한 2번째 피보나치 수부터 $10^5$ × 15번째 피보나치 수를 1,000,000으로 나눈 나머지를 이용하여 거기서 x번째 피보나치 수를 1,000,000으로 나눈 나머지를 찾으면 그 값이 답이 됩니다.