백준 2749번 : 피보나치 수 3 | JAVA

 

📌 알고리즘 선택

피보나치 수는 dp를 활용하여 fibo[i] = fibo[i-1] + fibo[i-2]의 값을 구할 수 있다는 것을 익히 알고 있었다. 그런데 ,, 문제에서 주어지는 n 값의 범위가 너무 커서 그냥 반복문을 돌리면 분명히 시간초과가 나기에,, 어떻게 규칙을 찾아야 하는지에 대해 중점적으로 고민했다.

 

---

📌 풀이

우선 피보나치 수를 담을 배열에는 1,000,000으로 나눈 나머지의 값을 담아 수의 크기를 줄이는 것은 쉬웠다.

하지만 피보나치 수의 규칙을 찾는 것은 꽤 어려웠다. 규칙을 찾고 싶어서 50번째까지 손으로 구해봤는데, 도무지 규칙이 나오지 않아 결국 피보나치 수의 규칙에 대해 검색해봤다.

 

'피사노 주기(pisano period)' 라고 피보나치 수를 나눈 나머지는 주기를 가진다는 규칙이 있었다.

주기를 P라고 하고, 피보나치 수를 나누는 수를 M이라고 할 때,

M = 10^k (k>2) 일 때, P = 15 * 10^(k-1) 이다.

 

따라서 피보나치 수를 1,000, 000으로 나눈다면 1,500,000번을 주기로 똑같은 나머지 값이 주어진다.

 

피사노 주기만 안다면, 간단히 구할 수 있는 문제였다.

(대부분 피사노 주기에 대해 모를 것이라 생각한다 .. 이 문제가 골드2인 이유인가 ..)

 

---

📌 코드

import java.io.IOException;
import java.util.Scanner;

public class Main {

    // 1,000,000(백만)으로 나눈 나머지를 출력
    public static void main(String[] args) throws IOException {

        Scanner sc = new Scanner(System.in);
        int pisano = 1500000;
        long[] fibo = new long[pisano+1];
        long n = sc.nextLong() % pisano;


        fibo[0] = 0;
        fibo[1] = 1;
        for(int i = 2; i <= pisano; i++) {
            fibo[i] = (fibo[i-1] + fibo[i-2]) % 1000000;
        }

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

    }

}