백준 10826 피보나치수4 파이썬

링크 : https://www.acmicpc.net/problem/10826

문제

그냥 간단한 DP다

n은 10000까지 주어지는데, 일반적인 방법으로 피보나치수를 구하게 되면 F(10000) = F(9999) + F(9998) = F(9998) + F(9997) + F(9997) + F(9996) = …

이런식으로 쭉쭉쭉 늘어가면서 결국 메모리제한256MB를 넘길것이다. 그래서 우린 DP를 해야한다

dp[2] = dp[1] + dp[0]

코드

import sys 
input =sys.stdin.readline 
n= int(input().strip())

dp = [ 0 for _ in range(n+1)]
dp[0] = 0

if n < 2 :
    print(n) 
else : 
    dp[1] = 1

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

    print(dp[-1])