[Python | 2156] 포도주 시식

https://www.acmicpc.net/problem/2156

---

문제 설명

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

 

📌 시간 제한: 2초

---

입력

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1 ≤ n ≤ 10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

---

출력

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.

---

문제 접근

처음 문제를 접하면, 단순히 양이 많은 포도주부터 고르면 될 것 같지만 “연속 3잔을 마시면 안 된다”는 제약 때문에 단순한 탐욕법(greedy)으로는 최적의 해를 보장할 수 없다.

 

예를 들어, 다음과 같은 포도주가 있다고 가정해 보자:

[ 6, 10, 13, 9, 8, 1 ]

 

양이 많은 순서대로 고르면 13 → 10 → 9를 마시게 되고, 연속 세 잔을 마시는 경우가 발생할 수 있다. 따라서 단순히 큰 값을 고르는 방식은 제약 조건을 만족시키지 못하거나, 최대값을 놓치게 된다.

이 문제는 이전에 어떤 잔을 마셨는지에 따라 다음 선택이 제한되므로, 이전 상태 정보를 활용해 최적해를 쌓아가는 동적 프로그래밍(DP) 방식이 적합하다.

 

💡 DP 테이블 정의

먼저 DP 테이블을 다음과 같이 정의한다:

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

이때, i번째 잔을 마실 수도 있고, 마시지 않을 수도 있기 때문에 다양한 선택지를 고려해야 한다.

 

🧠 상태 정의 및 점화식

i번째 잔을 기준으로, 마시는 경우는 다음 세 가지로 나눌 수 있다:

1. 현재 잔을 마시지 않는다
   • dp[i-1]
2. (i-1)번째 잔을 건너뛰고, i번째 잔을 마신다
   • dp[i-2] + wine[i]
3. (i-2)번째 잔을 건너뛰고, (i-1)번째와 i번째 잔을 연속으로 마신다
   • dp[i-3] + wine[i-1] + wine[i]

따라서 점화식은 다음과 같다:

dp[i] = max(
    dp[i-1],
    dp[i-2] + wine[i],
    dp[i-3] + wine[i-1] + wine[i]
)

 

초기 조건(0-based 인덱스 가정)은

• n == 1일 경우: wine[0]
• n == 2일 경우: wine[0] + wine[1]
• n >= 3일 경우:
  • dp[0] = wine[0]
  • dp[1] = wine[0] + wine[1]
  • dp[2] = max(wine[0]+wine[1], wine[0]+wine[2], wine[1]+wine[2])

---

구현

바텀업 방식

n = int(input())
wine = [int(input()) for _ in range(n)]

# 포도주 잔이 1개인 경우: 무조건 마신다
if n == 1:
    print(wine[0])

# 포도주 잔이 2개인 경우: 두 잔 모두 마셔도 됨
elif n == 2:
    print(wine[0] + wine[1])

# 포도주 잔이 3개 이상인 경우
else:
    dp = [0] * n  # dp[i]: i번째 잔까지 고려했을 때 최대 마실 수 있는 포도주 양

    # 초기 조건 설정
    dp[0] = wine[0]                          # 첫 번째 잔만 마신 경우
    dp[1] = wine[0] + wine[1]                # 첫 번째 + 두 번째 잔 마신 경우
    dp[2] = max(
        wine[0] + wine[1],                   # 1 + 2번 마신 경우
        wine[0] + wine[2],                   # 1 + 3번 마신 경우
        wine[1] + wine[2]                    # 2 + 3번 마신 경우
    )

    # 점화식 적용: i번째 잔까지 고려하며 최대값 갱신
    for i in range(3, n):
        dp[i] = max(
            dp[i-1],                         # 현재 잔을 마시지 않는 경우
            dp[i-2] + wine[i],              # 전전 잔 + 현재 잔
            dp[i-3] + wine[i-1] + wine[i]   # 전전전 잔 + 전 잔 + 현재 잔 (연속 3잔 방지)
        )

    print(dp[n-1])

 

탑다운 방식 (재귀 + 메모이제이션)

import sys
sys.setrecursionlimit(10000)

n = int(input())
wine = [int(input()) for _ in range(n)]

# 메모이제이션 테이블 (초기값 -1)
dp = [-1] * n

def max_wine(i):
    # 기저 조건 처리
    if i == 0:
        return wine[0]
    if i == 1:
        return wine[0] + wine[1]
    if i == 2:
        return max(wine[0] + wine[1], wine[0] + wine[2], wine[1] + wine[2])

    # 이미 계산된 값이면 반환
    if dp[i] != -1:
        return dp[i]

    # 점화식 적용
    dp[i] = max(
        max_wine(i-1),                      # 현재 잔을 마시지 않는 경우
        max_wine(i-2) + wine[i],            # 전전 잔 + 현재 잔
        max_wine(i-3) + wine[i-1] + wine[i] # 전전전 잔 + 전 잔 + 현재 잔
    )
    return dp[i]

print(max_wine(n-1))