[백준 알고리즘] 2749번(피보나치 수3)

[백준 알고리즘]

피보나치 수열을 오늘 모두 풀어보기 위해 다음 문제를 보겠습니다.

이 문제는 피보나치 수열에 N번째 피보나치 수를 1,000,000으로 나눈 값을 구하는 문제입니다.

그냥 단순하게 생각하고 N번째 피보나치 수에 1,000,000으로 나누니 출력이 안나오더라구요

역시나 이렇게 쉬운 문제가 아니였습니다.

그래서 이리저리 해봤지만 안되서 구글링해봤습니다.

구글링해보니 한 가지 더 알아야 할 것이 있더라구요

그래서 거기에 대해 먼저 설명을 좀 하겠습니다.

일단, 피사노 주기(Pisano Period)를 기억하셔야 합니다.

피사노 주기는 피보나치 수를 K로 나눴을 때 그 나머지가 항상 주기를 가진다는 말입니다.

예를 보시겠습니다.

이렇게 일정한 주기를 가지게 됩니다.

이 주기는 규칙을 가집니다

주기 길이를 P라고 하면  N번째 피보나치 수를 K로 나눈 나머지는 N%P번째 피보나치 수를 K로 나눈 나머지와 같다. [ fibo(N) % K = fibo(N%K) % K ]

그렇다면 N = 10 이고 K = 3 / P = 8 이라고 하면

fibo(10) % 3 = fibo(10%8) % 3   -> 34 % 3    =  fibo(2) % 3 

                                           -> 1 = 1

이렇게 같게 된다. 그렇다면 여기서 또 문제점이 생깁니다.

N 과 K는 그 값을 구할 수 있습니다. 그렇다면 주기 길이는 어떻게 구할까요?

(K : 나누는 수 / P : 주기 길이) 

표로 나타내면 이렇게 됩니다. 그러면 이제 규칙을 찾아야하는데

딱 보이는 규칙은 없습니다. 

하지만 위키백과사전에 보면 영어로 적힌 규칙이 있습니다(https://en.wikipedia.org/wiki/Pisano_period)

12를 구하는 것을 보게되면 

12 = 3 *  4 이고 3의 피사노 주기 값과 4의 피사노 주기 값의 최소공배수를 구하면 됩니다.

즉, 3 피사노 주기 값은 8 이고 4 피사노 주기 값은 6이므로 최소공배수는 24가 됩니다.

12 = 2 * 6도 됩니다 3과 24의 최소공배수는 마찬가지로 24입니다.

이렇게 값을 구할 수 있지만 7이나 13와 같은 소수는 그 값을 구하기 힘듭니다.

위키백과사전에도 너무 어렵게 설명이 되어 있습니다.

그래서 조금 간단히 생각해보겠습니다.

다시 위로 올라가서 피사노 주기를 보겠습니다.

<피사노 주기>

3으로 나눴을 때를 예로 들겠습니다.

그렇다면 우리는 fibo(N) % 3 의 값을 구하는 것입니다.

이것은 다시 (fibo(N-2) + fibo(N-1)) % 3 이 되고 이 것은 다시 ((fibo(N-2) % 3) + (fibo(N-1) % 3)) % 3 이렇게 

바꿀 수 있습니다.

조금 더 쉽게 숫자를 넣어보면

fibo(4)의 피사노 주기는 ((fibo(3) % 3) + (fibo(2) % 3)) % 3 = (2 + 1) % 3

                                                                            = 0

이해되겠습니까?

여기까지 이해 했으면 다 피사노 주기 다 아신겁니다.

import java.util.Scanner;
 
public class Beak2748 {
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] list = new long[n+1];
        int mod = 1000000;
        int period = pisano_period(mod);
        list[0] = 0;
        list[1] = 1;
        for (int i = 2; i < list.length; i++) {
            list[i] = list[i - 2] + list[i - 1];
            list[i] %= mod;
        }
        System.out.println(list[n % period]);
    }
 
    public static int pisano_period(int m) {
        int period = 0;
        int number1 = 1, number2 = 1;
        do {
            int temp = number1;
            number1 = number2;
            number2 = (temp + number2) % m;
            period++;
        } while (!(number1 == 1 && number2 == 1));
        return period;
    }
}
 

아래 pisano_period는 당연히 피사노 주기 구하는 알고리즘입니다.

이렇게 하면 문제를 풀 수 있을 것입니다.

한가지 Scanner를 이용하여 제출하니 런타임 에러가 나서 

BufferedReader를 사용하여 입력받으시면 될 겁니다.