[백준 알고리즘] Q2749 피보나치수 - 3 - 피사노주기

1. Java 구현

            
import java.util.Scanner;

public class Main {

	private static final int PERIOD = 1500000;
	private static final int DIVIDE = 1000000;

	public static void main(String[] args) {
		System.out.println(fibonacci(new Scanner(System.in).nextLong(), PERIOD, DIVIDE));
	}

	public static int fibonacci(long number, int period, int divide) {
		if(number <= 1) return (int)number;
		int[] fibonaccis = new int[(int)(number % period) + 1];
		fibonaccis[1] = fibonaccis[2] = 1;

		for (int i = 3; i < fibonaccis.length; i++)
			fibonaccis[i] = (fibonaccis[i - 2] + fibonaccis[i - 1]) % divide;

		return fibonaccis[fibonaccis.length - 1];
	}

}

2. 코드설명

 피보나치수를 구하는 방법에는 여러가지가 있다. 재귀를 활용할 수 있고, 메모리제이션을 활용할 수 있다. 개인적으로 재귀는 스택 오버 플로우가 발생할 수 있는 가능성이 

 존재하기 때문에 개인적으로 선호하지 않는다. 그래서 메모리제이션을 주로 사용한다. 하지만, 이번 문제에서는 단지 메모리제이션만 사용할 경우에는 시간초과 발생한다.

 수가 너무 크다. int로 담을 수 없고, long으로 담아야할 정도로 숫자가 크다. 그렇기 때문에 이와 같은 경우에는 피사노 주기를 사용해야 한다.

 솔직히, 피사노 주기를 증명하지는 못한다. 그냥 피사노 주기를 결과적으로 알뿐이다. 알았더라면 더 좋을거 같다. 혹시 아시는 분은... 댓글로 설명이나 링크 부탁드립니다.

 피사노 주기가 무엇이냐! K(10^n) = 15 * 10^(n - 1) 이다. 피보나치수를 특정 수로 나눈 나머지는 일정한 주기를 가진다. 

 예를들어, 피보나치를 10^5으로 나눈 나머지는 15 * 10^4의 주기를 갖는다. 따라서, fibo[1] % 100,000 == fibo[150000 + 1] % 100,000 과 같다. 일정한 주기를 가지니까!

3. Pain Point

 이 문제는 처음 알고리즘 공부를 할 때, 풀지 못했던 문제이다. 코드를 보니까 정말 다양한 방법으로 접근했지만, 결국 피사노 주기를 사용하지 않으면  풀 수 없었던 문제였다.

 그리고 피사노 주기의 증명은 잘 모르겠다.