문제
https://www.acmicpc.net/problem/2749
접근
- 문제에서 주어지는 N의 범위가 매우 크기 때문에, 피보나치 수들에 어떠한 주기가 있을 것으로 판단하고 구글 검색 후 피사노 주기라는 개념을 알게 되었다.
피사노 주기
def) In number theory, the nth Pisano period, written as π(n), is the period with which the sequence of Fibonacci numbers taken modulo n repeats.
즉, 주기를 p라고 했을 때, n번째 피보나치 수를 m으로 나눈 나머지는 n % p번째 피보나치 수를 m으로 나눈 나머지와 같다.
prop) 나누는 수 m이 10의 k승 꼴일 경우, 주기는 항상 15 * (10 ^ (k - 1)) 이다.
풀이
- 해당 문제에서는 m이 10의 6승 이므로, 주기는 15 * (10 ^ 5)이다.
n = int(input())
n %= 15 * (10 ** 5)
d = [0] * (n + 1)
if n == 0:
print(0)
else:
d[1] = 1
for i in range(2, n + 1):
d[i] = (d[i - 1] + d[i - 2]) % 1000000
print(d[n])
'Python > Coding Test' 카테고리의 다른 글
9996 한국이 그리울 땐 서버에 접속하지 (0) | 2022.02.17 |
---|---|
10165 버스 노선 (0) | 2022.02.17 |
21939 문제 추천 시스템 Version 1 (0) | 2022.02.16 |
13334 철로 (0) | 2022.02.15 |
2485 가로수 (0) | 2022.02.14 |