백준 2749번: 피보나치 수 3

문제 출처: https://www.acmicpc.net/problem/2749

참고: https://png93.github.io/baekjoon-2749-fibonacci/

피보나치 수를 나눈 나머지는 항상 주기를 가진다. 이를 피사노 주기(Pisano Period)라 한다.

그림 출처: http://nackwon.tistory.com/52

피보나치 수를 나눌 수를 K라고 할 때,이면, 피사노 주기는 이다.

즉, k가 10의 6승인 1,000,000이면 피사노 주기는 1,500,000이다.

1,500,000번째 까지의 피보나치 수를 1,000,000로 나눈 나머지 값들을 구하면 그 이후의 수는 계산할 필요가 없다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(reader.readLine());
        int pisano = 1500000; // 피사노 주기
        long[] arr = new long[pisano];
        arr[0] = 0; arr[1] = 1;
 
        for(int i=2 ; i<pisano && i<=n ; i++){
            arr[i] = (arr[i-1] + arr[i-2]) % 1000000;  // 피보나치 수를 1,000,000 으로 나눈 나머지 값을 저장 
        }
 
        if(n >=pisano){
            n %= pisano;
        }
 
        System.out.println(arr[(int) n]);
    }
}