[Baekjoon] 피보나치 수 3(python)

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

문제 접근

지금까지 피보나치 수열을 구하는 문제를 풀었을 때는 다음과 같은 방법으로 풀었다.

 

1. 재귀를 이용한 방법

def fibonacci(N):
    if N <= 1:
        return N
    else:
        return fibonacci(N - 1) + fibonacci(N - 2)

 

2. DP를 이용한 방법

dp = [0] * (N + 1)

dp[1] = 1

for i in range(2, N + 1):
    dp[i] = dp[i - 1] + dp[i - 2]

하지만 문제에서 주어진 N의 크기가 무려 1,000,000,000,000,000,000이다.

 

재귀를 이용해서 풀면 시간 초과이고 DP를 이용해서 풀면 메모리 초과이다.

 

따라서 다른 방법으로 문제를 해결해야 했고

 

검색해보니 피보나치 수열을 구하는 또다른 방법인 피사노 주기를 이용하여 문제를 푼 케이스가 많은 것 같다.

 

피사노 주기는 피보나치 수열을 K로 나눈 나머지는 특정 주기를 갖는다는 원리이다.

 

---

풀이 과정

이 문제는 피보나치 수열의 N번째 값을 1,000,000으로 나눈 나머지를 구하는 것이다.

 

즉, 위에서 말한 피사노 주기의 K값이 1,000,000이 되는 것이다.

 

Fibonacci(0) = 0, Fibonacci(1) = 1 이므로 피보나치 수열을 구하면서 0, 1이 다시 돌아오는 주기를 구하면 시간과 메모리를 초과하지 않고 문제를 해결할 수 있다.

---

정답 코드

"""
    백준 2749번 피보나치 수 3
"""
import sys


N = int(sys.stdin.readline())

fibo = [0, 1]
i = 2

# 피사노 주기는 피보나치 수열의 특정 주기가 있다는 것이다. 그렇다고 굳이 주기를 구할 필요는 없다.
while True:
    fibo.append((fibo[i - 1] + fibo[i - 2]) % 1000000)

    if fibo[i - 1] == 0 and fibo[i] == 1:
        break

    i += 1

print(fibo[N % (i - 1)])