[백준 Baekjoon] 2749번 피보나치 수 3 - JAVA

백준 Baekjoon 2749번 피보나치 수 3 - JAVA

---

문제 풀이

피보나치 수의 개념을 알고 여러 문제들을 풀어봤지만, 이번 문제처럼 큰 입력은 처음으로 주어졌다. 메모리제이션을 하고 최대한 시간초과가 나지 않게 하려 해도 불가능하여 검색을 해보니 피사노라는 피보나치의 속성이 있고, 이를 활용하여 문제를 풀 수 있었다.

소스 코드

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

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

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

        int pisano = 1_500_000;
        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]) % 1_000_000;
        }

        System.out.println(arr[(int) ( n % pisano)]);
    }
}