[BOJ 2749] 피보나치 수3 - Python 풀이

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 1,000,000으로 나눈 나머지를 출력한다.

코드

import sys
## 피보나치 수를 나눌 수. 10^6
M = 1000000 
## 주기의 길이. 15*10(6-1)
P = 15*pow(10,5)

def get_fibonacci_number(N):
    fibo = [0,1]
    for i in range(2, P):
        fibo.append(fibo[i-2]+fibo[i-1])
        fibo[i] %= M
    return(fibo[N%P])

if __name__ == "__main__":
    N = int(sys.stdin.readline())
    print(get_fibonacci_number(N))

결과

풀이

알고리즘 자체는 굉장히 쉬우나, 피사노 주기를 사용한다는 아이디어가 어려운 문제이다.

피사노 주기란 "피보나치 수를 K로 나눈 나머지는 항상 주기를 갖게되며, 주기의 길이가 P일 때, N번째 피보나치 수를 M으로 나눈 나머지는 N%P번째 피보나치 수를 M을 나눈 나머지와 같다. M = 10^k일 때, k>2라면 주기는 항상 15*10^(k-1)가 된다"는 원리이다. (링크 <- 참고)

 

처음에 이것을 읽었을 때 .. 음 .. 그래서 이게 뭐 어쨌다고 .. ;; 했다.

그래서 이것을 이 문제에 어떻게 적용했는지 링크의 코드를 보면서 이해하려고 노력했고,

결론부터 말하자면 이 문제에서 M은 1000000이 되므로 k는 6이고, 따라서 주기의 길이 P는 15*10^5가 된다.

 

그리고 이 주기 동안 피보나치 수에 1000000을 나눈 나머지를 저장한 배열을 구했고,  입력받은 수인 N번째 피보나치 수가 아닌 N%P번째 피보나치 수를 반환하여 구했다.

 

지수를 이용한 다른 풀이도 있는 것 같은데 그 방법으로도 풀어보아야겠다.