1️⃣서론
백준 문제 2749번 피보나치 수 3 입니다. 파이썬(Python)으로 풀었습니다.
2️⃣문제 설명
이 문제는 피보나치 수를 구하는 문제입니다.
하지만 N의 크기가 1,000,000,000,000,000,000 이하여서 난해했던 문제입니다.
3️⃣풀이
피보나치 수를 구하는 방법은 여러가지가 있는데요
일반적인 피보나치 수의 공식은 다음과 같습니다.
n = 0, 1일때 각각 0, 1 이라고 하면 fibo[n] = fibo[n-1] + fibo[n-2] 입니다.
이와 같은 공식은 메모이제이션을 추가해 O(N)의 방법으로 가능합니다.
하지만 이 방법은 이 문제에서는 통용되는 방법이 아닙니다. N이 매우 크기 때문입니다.
그래서 여기서는 피사노 주기라는 방법을 사용합니다.
피사노 주기는 피보나치 수를 K로 나눈 나머지는 항상 주기를 갖게된다는 원리입니다.
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| $F_{n}$ | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | 144 | 233 | 377 | 610 |
| $F_{n}\mod3$ | 0 | 1 | 1 | 2 | 0 | 2 | 2 | 1 | 0 | 1 | 1 | 2 | 0 | 2 | 2 | 1 |
주기의 길이가 P 일 때, N번째 피보나치 수를 M으로 나눈 나머지는 N%P번째 피보나치 수를 M을 나눈 나머지와 같습니다.
$M =10^{k}$ 일 때, k > 2 라면, 주기는 항상 $15 * 10^{k-1}$ 입니다.
이와 같은 식을 보고 소스코드를 보도록 하겠습니다.
또한, 피보나치 수에 대하여 좀 더 알고 싶으시다면 백준님이 쓰신 블로그를 참조해주세요!
4️⃣ 소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
# 주기의 길이가 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])
5️⃣ 마치며..
질문과 지적은 환영합니다. 이 문제는 최적의 정답일 수도 아닐수도 있습니다.
궁금한게 있으시면 아래 댓글 남겨주세요.🙏
댓글은 저에게 큰 힘이 됩니다!
감사합니다. ❤️
