[BOJ / PYTHON] 2156. 포도주 시식

from sys import stdin

input = stdin.readline

N = int(input())

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

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

dp[1][0] = 0
dp[1][1] = arr[0]

if N > 1:
    for i in range(2, N+1):
        dp[i][0] = max(dp[i-1])
        dp[i][1] = dp[i-1][0] + arr[i-1]
        dp[i][2] = dp[i-1][1] + arr[i-1]

print(max(dp[-1]))

풀이.

계단 오르기 문제와 매우 유사한 문제이다.
단, 조건이 연속해서 뛰어 넘을 수 있다는 조건만 다르다.
즉, 이전에 포도주를 마시지 않았다고 해서 반드시 마실 필요가 없는 것이므로, 이전 dp의 최대 값을 dp[i][0] 번째에 넣어준다.
다른 부분은 동일하게 알고리즘을 작성한다.