조금 까다로웠던 DP

DP의 늪에서 벗어나질 못하는중....

 

#2156번 포도주 시식 https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

1차원 행렬에 있는 숫자를 최댓값이 되도록 선택하는 문제이다.

조건은 딱 하나 연속으로 3개의 수를 선택할 수 없다는 점.

 

약간 골치아팠던 문제이다.

 

 

import sys
n = int(sys.stdin.readline())
wines = []
for i in range(n):
    wines.append(int(sys.stdin.readline()))

dp = [0]*n
# 3번째 항 까지는 기본적으로 넣어준다.
if n == 1:
    dp[0] = wines[0]
elif n == 2:
    dp[0] = wines[0]
    dp[1] = wines[0] + wines[1]
else:
    # 첫번째 와인을 마신 경우
    dp[0] = wines[0]
    # 첫번째 와인과 두번째 와인을 마신 경우
    dp[1] = dp[0] + wines[1]
    # 세번째 와인을 마시지 않은 경우 or 첫번째 와인을 마시지 않은 경우, or 두번째 와인을 마시지 않은 경우
    dp[2] = max(dp[1], wines[2] + wines[1], wines[2] + dp[0])

for i in range(3, n):
    # 4번째 와인 + 2번째 이전 와인까지의 합
    case1 = wines[i] + dp[i-2]
    # 4번째 와인 + 세번째 와인까지의 합
    case2 = wines[i] + wines[i-1] + dp[i-3]
    # 4번째 와인을 마시지 않음 -> 2, 3번째 와인의 합
    case3 = dp[i-1]
    dp[i] = max(case1, case2, case3)

print(dp[n-1])