[백준] 2749번: 피보나치 수 3 - java

문제

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

2749번: 피보나치 수 3

 

접근법

문제 제목만 보고 피보나치 수는 금방 풀 수 있겠지~ 했는데 역시 골드 2인 이유가 있었다. 피사노 주기를 알아야 풀 수 있는 문제였다. 

 

피사노 주기 (Pisano period)

: 피보나치 수를 어떤 수 K로 나눌 때, 나머지는 항상 주기를 가지게 된다. 

주기의 길이를 P라고 할 때 N번째 피보나치 수를 M으로 나눈 나머지는 N%P번째 피보나치 수를 M으로 나눈 나머지와 같다.
주기는 M = $10^k$일 때, 항상 $15*10^(k-1)$이다.

 

문제에서 1,000,000으로 나눈 나머지를 출력하라고 했으므로 $M=1,000,000=10^6$이다.

따라서 주기 $P=15*10^5=1,500,000$이다.

 

코드

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

public class Main {

    static final int P = 1_500_000; // 주기
    static final int M = 1_000_000; // 나누는 수
    static long n;

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

        n = Long.parseLong(br.readLine());

        int[] fibo = new int[(int)(n % P) + 1];
        fibo[0] = 0;
        fibo[1] = 1;

        for (int i = 2; i < fibo.length; i++){
            fibo[i] = (fibo[i - 2] + fibo[i - 1]) % M;
        }

        System.out.println(fibo[(int)(n % P)]);
    }
}

n의 범위가 int를 넘어가기 때문에 long으로 선언해야 한다.

피보나치 연산을 할 때마다 모듈러 연산을 해주어야 하는 것도 유의하자.