[파이썬/Python] 백준 2156번: 포도주 시식

📌 문제 : 백준 2156번

---

📌 문제 탐색하기

n : 포도주 잔의 수 $(1 ≤ n ≤ 10,000)$
glasses : 포도주의 양 $(0 ≤ wine_{i} ≤ 1,000)$

n개의 포도주 잔에 들어있는 포도주 양을 규칙에 따라 마실 때, 최대로 마실 수 있는 포도주 양을 구하는 문제이다.

문제 풀이

⭐️ 포도주 시식의 규칙

• 선택한 포도주 잔은 모두 마시고 제자리에 돌려놓아야 한다.
• 연속으로 놓인 3잔을 모두 마실 수는 없다.

규칙에 따라 포도주를 마실 수 있는 방법은 다음과 같다.
특히, 두번째 규칙에 유의해야 한다.

현재 위치가 i번째 잔이라 하고,
그 잔을 마신다고 가정한다면 3잔 연달아 마실 수 없으므로
1️⃣ i-1번째 잔 마시고 i-3번째 잔 마시기
2️⃣ i-2번째 잔 마시고 i-1번째 잔 마시지 않기

만약 i번째 잔을 마시지 않는 경우,
3️⃣ 그 이전까지 최대로 마신 포도주의 양을 그대로 이용하면 된다.

최대로 마실 수 있는 포도주의 양을 구해야 하기 때문에
저 3가지 방법 중 더 큰 값을 이용하도록 하면 될 것이다.
이를 DP로 구현한다.

⭐️ DP 테이블 정의 & 초기화
i = 0
→ 맨 첫번째 잔만 마실 수 있다 ﹦ dp[0] = glasses[0]
i = 1
→ 첫번째, 두번째 잔 마실 수 있다 ﹦ dp[1] = glasses[0] + glasses[1]
i = 2
→ 3가지 경우 모두 가능하다 (1️⃣번 경우를 위해 dp[2]까지 계산) ﹦ dp[2] = max(glasses[2] + glasses[1], glasses[2] + glasses[0], dp[1])

지난번 계단 오르기 문제에서 n의 크기를 고려하지 않고 dp 테이블을 채워서 IndexError가 발생한 적이 있다.
이 문제도 dp 테이블을 dp = [0] * n로 정의했기 때문에
입력된 n의 크기에 따라 테이블을 채우도록 구현해야 한다.

가능한 시간복잡도

DP 테이블 채우기 → $O(n)$

최종 시간복잡도
총 $O(n)$이 된다.
최악의 경우 $O(10^4)$이므로 이는 2초 내에 연산이 가능하다.

알고리즘 선택

DP로 최대의 포도주 양 구하기

DP 구현

1️⃣ dp 테이블를 정의한다.
2️⃣ dp 테이블의 초기값 계산한다.
3️⃣ 조건에 따라 dp 테이블을 채워준다.
4️⃣ dp 테이블의 마지막 값을 출력한다.

---

📌 코드 설계하기

1. n 입력
2. glasses 입력
3. dp 테이블 만들기
4. dp 테이블 채우기
5. 결과 출력
   
   

---

📌 시도 회차 수정 사항

1회차

print(dp[n])

• dp[n]을 정답으로 출력했더니 IndexError가 발생했다.
• dp 테이블을 인덱스 0부터 채웠기 때문에 n-1로 접근해야 했는데 헷갈렸다.

---

📌 정답 코드

import sys

input = sys.stdin.readline

# n 입력
n = int(input())

# glasses 입력
glasses = [int(input()) for _ in range(n)]

# dp 테이블 초기화
dp = [0] * n

# dp 테이블 채우기
dp[0] = glasses[0]

if n > 1:
    dp[1] = glasses[0] + glasses[1]

if n > 2:
    dp[2] = max(glasses[2] + glasses[1], glasses[2] + glasses[0], dp[1])

if n > 3:
    for i in range(3, n):
        dp[i] = max(dp[i-3] + glasses[i-1] + glasses[i], dp[i-2] + glasses[i], dp[i-1])

# 정답 출력
print(dp[n-1])

• 결과