[DP/동적계획법] 백준 2749 피보나치 수 3 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

2749번: 피보나치 수 3

 

 

 

2. 문제 풀이

 N번째 피보나치 수를 구하는 문제입니다.

 

2022.02.13 - [Algorithm] - [DP/동적계획법] 백준 2748 피보나치 수 2 - Python

[DP/동적계획법] 백준 2748 피보나치 수 2 - Python

 피보나치 수 2 문제와 동일하지만, 메모리 제한이 128MB이고 입력이 1,000,000,000,000,000,000보다 작은 n이 주어집니다. 상당히 큰 수이기 때문에, 동적계획법만 사용하면 메모리 초과가 뜹니다.

 

피사노 주기(Pisano period): 어떤 수를 K로 나눌 때, 나머지는 항상 피사노 주기를 따름 

 

 피사노 주기라는 걸 이용해서 풀어야 합니다. 주기를 P라고 했을 때, N번째 피보나치 수를 M으로 나눈 나머지는 N%P번째 피보나치 수를 M으로 나눈 나머지와 같다고 합니다.

 개인적으로 세부적인 수학 개념이 필요한 문제는 별로 좋아하진 않습니다. 이런 개념이 있다는 정도만 알아두고, 구현하면 풀 수 있습니다. 

 

 

 

3. 코드

N = int(input())

mod = 1000000
fibo = [0, 1]
p = mod//10*15 # 피사노 주기

for i in range(2,p):
    fibo.append(fibo[i-1]+fibo[i-2])
    fibo[i] %= mod

print(fibo[N%p])