[BOJ / PYTHON] 2579. 계단 오르기

import sys

input = sys.stdin.readline

N = int(input())

arr = list(int(input()) for _ in range(N))

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

for i in range(1, N+1):

    dp[i][0] = max(dp[i-1][1], dp[i-1][2])
    dp[i][1] = dp[i-1][0] + arr[i-1]
    dp[i][2] = dp[i-1][1] + arr[i-1]

print(max(dp[-1][1], dp[-1][2]))

풀이.

기초적인 최소 비용 계단 오르기 문제와 유사한 형태의 문제이다.
다만 다른 점은, 최대 비용을 구해야하며 추가적인 조건이 존재한다.
해당 조건을 적용시키기 위해서, DP 테이블을 1차원 형태로 만들지 말고, 2차원 형태로 만들어 해결한다.
이전 상태가 3가지 (밟지 않은 경우, 1계단 오른 경우, 2계단 오른 경우)로 존재하기 때문이다.

최소 비용 계단 오르기