백준 2579 계단 오르기

과정

• DP. 비슷한 문제: 2156 포도주 시식
• 현재 위치를 밟은 경우의 최대값을 DP에 저장하기
• i번째를 밟는다고 했을 때 가능한 경우는 i-2, i를 밟기, i-3, i-1, i를 밟기
  • dp[i-2] + lst[i], dp[i-3] + lst[i-1] + lst[i] 중 최대값 저장
• 영향을 받는 부분과 받지 않는 부분을 나누는 데에 주의해야한다.
  • 점화식 세우기 주의...

N = int(input())
lst = list(int(input()) for _ in range(N))
dp = [0 for _ in range(N)]

for i in range(N):
    if i == 0:
        dp[0] = lst[0]
    elif i == 1:
        dp[1] = max(lst[0] + lst[1], lst[0], lst[1])
    else:
        dp[i] = max(dp[i-2] + lst[i], dp[i-3] + lst[i-1] + lst[i])


print(dp[-1])