[Python] BOJ 2749번. 피보나치 수 3

작성일 | In |

2749번. 피보나치 수 3

문제 링크

풀이 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 2749번. 피보나치 수 3


n = int(input())
fibo = [0, 1]
mod = 1000000

# 피보나치 수를 나눈 수는 항상 주기를 가진다.
# 피보나치 수를 나눌 수를  k라고 할 때, k=10^n이면
# 주기는 15*10^(n-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])

비고