문제 출처 : https://www.acmicpc.net/problem/2156

문제 파악

• 포도주는 3잔 연속으로 마실 수 없다.
• 마지막 잔을 반드시 마실 필요는 없다.
• 목표: 0번 잔부터 i번 잔까지 고려했을 때 마실 수 있는 최대 양을 구하는 것.

dp[i] = i번째 포도주까지 고려했을 때 마실 수 있는 최대 양

가능한 선택은 3가지:

1) i번째 잔을 안 마시는 경우
→ dp[i-1]

2) i번째 잔만 마시는 경우 (i-1은 안 마심)
→ dp[i-2] + wines[i]

3) i-1, i번 잔을 연속으로 마시는 경우 (i-2는 못 마심)
→ dp[i-3] + wines[i-1] + wines[i]

이 3가지 중 최대값을 취한다.

해답 및 풀이

import sys
input = sys.stdin.readline

N = int(input())
wines = []
for _ in range(N):
    wines.append(int(input()))

# 연속 3잔 마실 수 없다.
# dp[i] = i번째 포도주를 마실때까지 최댓값
dp = [0]*10000  # N 최대 10,000

# N이 1 또는 2일 때는 바로 처리
if N == 1:
    print(wines[0])
    exit()

elif N == 2:
    print(wines[0] + wines[1])
    exit()

# 초기값
dp[0] = wines[0]
dp[1] = wines[0] + wines[1]

# 점화식
for i in range(2, N):
    dp[i] = max(
        dp[i-2] + wines[i],                # i 마시고 i-1 안 마심
        dp[i-3] + wines[i-1] + wines[i],   # i-1, i 마심
        dp[i-1]                             # i 안 마심
    )

print(dp[N-1])

처음에 앞서 풀었던 계단오르기 문제 비슷한듯 보였지만 맨 마지막 와인 또는 맨 마지막 전 와인 등 꼭 마지막 와인을 먹지 않아도 된다는 점에 차이가 있었다.

그래서 dp[i]를 정의할 때 dp[i-1] 과의 비교도 해주어야 전 dp배열값이 더 크면 현 dp배열값이 무시되며 덮어씌워지는, 스킬이 하나 더 추가된 문제였다.