백준 [ALGORITHM] - 피보나치 수2 (2748)

n = int(input())

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

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

print(dynamic(n))

기초적인 dp문제이다.

피보나치 수를 재귀로 구현하면 배열에서 입력받은 i의 함수 [i-2] + [i-1] 를

재귀적으로 호출해서 계산해야한다. 

이는 매우 비효율적이며 구해야하는 값이 커질수록 시간도 오래 걸린다.

 

따라서 dp를 이용하여 값을 저장하며 진행하면 시간이 더욱 단축된다.