[백준] 2749번. 피보나치 수 3 (Java)

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

2749번: 피보나치 수 3

 

문제 / 풀이

n 번째 피보나치 수열을 출력하는 문제다 

 

다만 n이 자료형으로 처리할 수 없을정도로 크기 때문에 숫자를 줄여야 하는데 

여기서 사용되는 것이 '피사노 주기' 이다 ( 참고 : https://chamggae.tistory.com/207 )

 

여기서 m 값은 1,000,000 이 되고 

피사노 주기를 풀었던 코드에 입력해도 되고 

• n > 2라면, k(10n) = 15×10(n-1) 을 사용해도 된다. 

 

피보나치 수열이 1,500,000 마다 주기를 이루기에 입력된 n 을 나눠서 구하면 된다. 

 

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

public class Main {
    
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(reader.readLine());
        long index = n % 1500000;
        
        long[] fb = new long[(int)index + 1];
        
        fb[0] = 0;
        fb[1] = 1;
        
        for(int i = 2; i <= index; i++) {
            fb[i] = (fb[i - 1] + fb[i - 2]) % 1000000;
        }
    
        System.out.println(fb[(int)index]);
    }
}