[Baekjoon] 백준 15624번 Python

백준 15624번

사전지식 : 동적프로그래밍(Dynamic Programming), 재귀함수(Recursion Function)

import sys
input = sys.stdin.readline

n = int(input())
dp = [0]*1000001
dp[0] = 0
dp[1] = 1

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

print(dp[n])

코드 설명

1. 시간 초과 방지용 sys
   
   
2. n이 0도 가능 하기때문에 피보나치 수 0,1번째 입력함 (dp[0] = 0, dp[1] = 1)
   
   
3. 이후 피보나치 수 점화식을 통해 이후 수 계산함
   
   
4. n의 범위가 너무 커서 메모리 문제가 발생하기때문에 반복문 안에서 값을 바로 나눠줌
   
   
5. n번째 피보나치 수(미리 나눠둔) 출력