[파이썬/python] 백준 10826번 : 피보나치 수 4 (🥈5) (feat.동적계획법/다이나믹프로그래밍)

n = int(input())
dp = [0,1]

for i in range(len(dp), n+1):
    dp.append(dp[i-2]+dp[i-1])
    
print(dp[n])

 

 

피보나치수열은 0과 1로 시작할 때, 이후의 숫자는 이전의 두 숫자를 더한 값으로 이루어지는 수열을 말한다.

 

n이 4라면

for 문의 범위는 (2, 5)

 

첫 번째 for 

dp.append(dp[2-2]+dp[2-1]) = dp.append(0+1)

=> dp = [0,1,1]

 

두 번째 for

dp.append(dp[3-2]+dp[3-1]) = dp.append(1+1)

=> dp = [0,1,1,2]

 

세 번째 for

dp.append(dp[4-2]+dp[4-1]) = dp.append(1+2)

=> dp = [0,1,1,2,3]

 

for 문 끝

 

print(dp[4]) => 3, 즉 네 번째 피보나치 수는 3이 된다.