[백준] 2749 : 피보나치의 수 3 (JAVA) / 피보나치 수 구하는 방법, 재귀, 메모이제이션, 행렬)

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

2749번: 피보나치 수 3

전형적인 피보나치 문제인데, 골2길래 뭔가 싶어 풀어봤다. 이 문제의 주의할 점을 몇가지 뽑자면

• 입력값 n의 크기가 10^18 로 매우 크다. int 형이 아닌 long 으로 입력을 받아야한다.
• n번째 피보나치 수를 구하기에, n이 매우 크므로 재귀방식이 아닌 행렬을 사용해풀어야 하지만 이 또한 n이 크기 때문에 O(n) 으로는 해결하기 애매하다. 1,000,000 으로 나눈 나머지를 출력한다는 부분이 힌트.
• 결론적으로 피사노 주기(Pisano Period)를 이용하여 풀어야하는 문제다.

 

피보나치 수를 구하는 방법

풀이에 앞서 피보나치 수를 구하는 방법을 간략히 정리해보겠다. 이미 알고있다면 넘겨도 된다.

재귀사용

public static int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fibonacci(n - 1) + fibonacci(n - 1);
}

한 함수는 두 개의 함수를 호출하게 되므로 시간 복잡도가 O(2^n) 정도이다.

재귀사용 + 메모이제이션

static int[] memo = new int[50];

public static int fibonacci(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (memo[n] != 0) return memo[n];
    return memo[n] = fibonacci(n - 1) + fibonacci(n - 1);
}

 

메모이제이션을 추가한 방법의 시간 복잡도는 O(N) 이다.

행렬사용

int[] fibo = new int[N+1];
fibo[0] = 0;
fibo[1] = 1;
for (int i = 2; i <= N; i++) {
    fibo[i] = (fibo[i - 1] + fibo[i - 2]);
}

위와 같이 간단하게 행렬을 사용할 수 있다. 이 또한 시간 복잡도는 O(N) 이다.

더 자세한 내용은 아래 링크를 참조하자

https://www.acmicpc.net/blog/view/28

피보나치 수를 구하는 여러가지 방법

---

피사노 주기(Pisano Period) 란?

피보나치 수를 K로 나눈 나머지는 항상 주기를 가지게 된다. 이를 피사노 주기(Pisano Period)라고 한다.
피보나치 수를 3으로 나누었을 때, 주기의 길이는 8이다.

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

이 문제에서 M = 10^6 이기 때문에, 주기는 15 × 10^5 = 1500000 이다.

 

---

public class P2749 {
    static long[] fibo;
    static final int pisano = 15 * 100000;

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

        N %= pisano;
        fibo = new long[(int) N + 1];
        fibo[0] = 0;
        fibo[1] = 1;
        for (int i = 2; i <= N; i++) {
            fibo[i] = (fibo[i - 1] + fibo[i - 2]) % 1000000;
        }
        System.out.println(fibo[(int) N]);
    }
}