[python/백준] 2749번: 피보나치 수 3

 

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

2749번: 피보나치 수 3

 

 

⭐ 문제

 

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

 N의 크기가 1,000,000,000,000,000,000 이하

 

 

 

⭐ 코드 분석

 

피보나치 수 : n = 0, 1일때 각각 0, 1 이라고 하면 `fibo[n] = fibo[n-1] + fibo[n-2]`

출처: 삼성디스플레이 뉴스룸

 

 

 

` 피사노 주기 ` : 피보나치 수를 K로 나눈 나머지는 항상 주기를 갖게된다는 원리

 

 

 

 

주기의 길이가 P 일 때, N번째 피보나치 수를 M으로 나눈 나머지는 N%P번째 피보나치 수를 M을 나눈 나머지와 같다

 

⭐ 코드

 

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])