백준 파이썬 2579 계단 오르기

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

대표적인 DP문제

 

너무 어렵게 생각하지말고

내가 지금 서있는 계단[i] + 계단[i-1] + 지금까지 올라왔던 dp계단[i-3] or 지금 내가 서있는 계단[i] + dp계단[i-2] 중 큰 수를 정하고 계단의 맨 위를 계산하면 됨.

 

n=int(input())
li=[0]
for i in range(n):
    li.append(int(input()))

if n == 1:
    print(li[1])
else:
    dp = [0] * (n+1)
    dp[1] = li[1]
    dp[2] = li[1] + li[2]

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