[백준 2749] - [분할정복 수학] - 피보나치 3

문제 링크 : https://www.acmicpc.net/problem/2749

---

이문제를 처음 보고 어떻게 10의 16승까지 풀지.. 하면서 멘붕에 이르렀고 

정말 순수하게 10의 16승까지 계산을 하고 돌려보니 결과를 받아볼 수 없었다.

즉.. 시간 초과에 걸리게 되는것..

정말 멘붕이었고 자존심을 버리고 구글링을 하였다.

이 문제는 피사노 주기 라는것을 이용해야 한다고 한다. 

나중에 피사노 주기에 대한 문제를 포스팅 해야겠다. 

피사노 주기에 대해서 간략하게 정리를 하면

피보나치 수열을 N 의 값으로 나눈 나머지는 일정한 주기를 가진다. 라고 한다. 

즉 m으로 나눈 나머지는 K(m) 개의 주기를 가지고 피보나치 수열을 K(m)개의 주기만큼만 구하면 된다는 것이다. 

이 문제에서는 m이 1,000,000이다. 

아직 피사노 주기에 대한 구하는 방법을 이해를 못했으니 소스는 올리지 않겠다.

그냥 이문제를 이해할 수 있는 범위내에서만 정리를 하겠다.

수식을 적어야 해서 아래의 조건을 확인하자.

즉 우리는 10의 6승으로 나눈 피보나치 수열을 구하고자 하고 그 주기는 1,500,000 의 주기로 피포나치 수열이 반복된다는것을 알 수 있다. 

그럼 우리는 피보나치 수열을 1,500,000 까지만 구하면 된다.

이문제는 소스를 짜는데 2분도 안걸렸지만 이해하는데는 한 두시간 정도 걸린거 같다..

피사노 주기를 먼저 이해하고자 했지만 너무 힘들었고 위의 조건을 이해하는데 까지 정말 오랜시간이 걸렸다.

알고리즘 문제를 풀다보면 자존감이 바닥으로 떨어지는걸 느낄수 있다.

오늘이 그날이다.. 

소스

import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long t = sc.nextLong();
        
        int DIV = 1000000;
        int pisano = 1500000;
        
        t = t%pisano;
        
        long[] fibo = new long[pisano+1];
        fibo[1] = 1;
        
        for(int i=2; i <= pisano; i++) {
            fibo[i] = (fibo[i-1] + fibo[i-2])%DIV;
        }
        
        System.out.println(fibo[(int)t]);
    }
}