피보나치 3 - PYTHON

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

출력

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

문제 풀이

처음에 너무 쉬운데 정답률이 20퍼,,? 라고 생각했던 적이 있다. 단순 dp문제로 생각했기 때문...... 🥲
예시로 1000을 줬는데 python 자체가 재귀 횟수에 제한을 두는데 그게 딱 1000으로 알고있다.. (문제 내신분 리스펙...)
물론 그 제한 횟수는 조정할 수 있는데 👇

import sys
sys.setrecursionlimit(10**7)

문제를 제한 사항이 어마무시한점을 보아하니 dp로 시간 복잡도는 획기적으로 줄일 수 있겠지만 메모리 초과...🤦‍♂️
실패 코드를 먼저 보겠다...

import sys
sys.setrecursionlimit(10**7)
num = int(input())
dp = [0] * (num +1)

def fibo(n):
  if n <=2 :
    return 1
  if dp[n] != 0:
    return dp[n]
  else:
    dp[n] = fibo(n-1) + fibo(n-2)
    return dp[n]

print(fibo(num)%1000000)

역시 문제 의도는 대표적 dp 문제에서 시간 및 공간 복잡도를 최소화 할 수 있겠냐?? 이걸 묻는거 같다..

이 문제 풀이에는 정말 상상도 못한 개념이 나오는데 백준 오피셜 피사노 주기 라는 피보나치 수를 K로 나눈 나머지는 항상 주기를 가지게 된다는 성질을 이용한 풀이 방법이었다.

자세한 내용은 여기 를 참조하고...

귀찮은 사람을 위해 요약하자면,
1. K로 나눴을 때 주기가 P라면, fibo(N) % K = fibo(N%P) % k
2. K = 10^k ( k > 2) 라면, P = 15*10^(k-1) 임.

이 두가지를 그대로 코드로 옮기면...

n = int(input())
a, b = 0, 1
p = 15*100000
#fibo(N) % K = fibo(N%P) % k 
n = n % p 
for _ in range(n):
    a, b = b%1000000, (a+b)%1000000
print(a)