[Baekjoon] 2156번: 포도주 시식(Dynamic Programming)

# Baekjoon 2156번: 포도주 시식

import sys
input = sys.stdin.readline

N = int(input())
cost = []
dp = [0] * N

for i in range(N):
    cost.append(int(input()))

if N == 1:
    dp[0] = cost[0]
elif N == 2:
    dp[1] = cost[0] + cost[1]
else:
    dp[0] = cost[0]
    dp[1] = cost[0] + cost[1]
    dp[2] = max(cost[0] + cost[2], dp[1], cost[1] + cost[2])

for i in range(3, N):
    dp[i] = max(dp[i-2] + cost[i], dp[i-3] + cost[i-1] + cost[i], dp[i-1])

print(max(dp))

 
 이번 문제는 Dynamic Programming 알고리즘 문제였다. 이 문제는 연속으로 세 잔을 마실 수 없다는 제한 때문에 동적 프로그래밍을 적용할 수 있다. 각 잔을 마시거나 마시지 않는 경우에 따라 최대 마실 수 있는 포도주의 양을 계산한다.
 dp[i]번째는 max(dp[i-2] + cost[i], dp[i-3] + cost[i-1] + cost[i], dp[i-1])로 구할 수 있다.
 
1. i번째 잔을 마시지 않는 경우: dp[i-1]
2. i번째 잔을 마시고, i-1번째 잔은 마시지 않고, i-2번째 잔을 마시는 경우: dp[i-2]+cost[i]
3. i번째 잔을 마시고, i-1번째 잔도 마시는 경우: dp[i-3]+cost[i-1]+cost[i]