[BOJ2156 - Python] 포도주 시식

문제

---

2156번: 포도주 시식

 

1부터 n까지 번호가 붙어 있는 n개의 포도주가 들어있는 잔이 일렬로 놓여있다.

포도주 시식에는 두 가지 규칙이 존재한다.

 

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.

2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

 

각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 최대로 마실 수 있는 포도주의 양을 구하는 것이 문제이다.

 

 

풀이

---

DP로 문제를 해결할 수 있다.

 

첫번째 시도 (실패)

1. 테이블 정의

dp[i] : i번째 포도주를 마셨을 때, 현재까지 마신 포도주 양의 최댓값

 

2. 점화식 찾기

포도주를 연속으로 3번 마실 수 없기 때문에, i번째 포도주를 마시기 위해서는 2가지 경우를 생각할 수 있다.

* wine : 각 포도주의 양이 저장되어 있는 배열

 

1. i-1번째 포도주를 마시지 않았을 경우 (i-2번째 포도주는 마심)

dp[i-2] + wine[i]

 

?

O

X

O

 

 

2. i-2번째 포도주를 마시지 않았을 경우 (i-3번째 포도주는 마심)

dp[i-3] + wine[i-1] + wine[i]

 

O

X

O

O

 

 

이 둘을 통해서 도출되는 점화식은 다음과 같다.

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

 

하지만 이렇게만 점화식을 세웠을 경우, 다음의 반례가 존재한다 ㅠㅠ

5 5 1 1 5 5

즉, 포도주를 연속 2번 마시지 않는 경우가 생각되지 않는 것이다.

 

두 번째 시도 (성공)

1. 테이블 정의

dp[i] : i번째 포도주를 마셨거나 마시지 않았을 경우, 현재까지 마신 포도주 양의 최댓값

 

2. 점화식 찾기

위의 첫 번째 시도에서 i번째 포도주를 마시기 위한 2가지 경우 + i번째 포도주를 마시지 않는 경우까지 생각해주어야 한다.

 

백준 질문 게시판에 좋은 설명이 있어서 남긴다.

글 읽기 - 와인을 마시지 않는 경우가 왜 필요한가요?

 

1. i-1번째 포도주를 마시지 않았을 경우 (i-2번째 포도주는 마심)

dp[i-2] + wine[i]

 

?

O

X

O

 

 

2. i-2번째 포도주를 마시지 않았을 경우 (i-3번째 포도주는 마심)

dp[i-3] + wine[i-1] + wine[i]

 

O

X

O

O

 

 

3. i번째 포도주를 마시지 않았을 경우

dp[i-1]에 저장되어 있는 값을 그대로 가져오면 된다.

 

?

?

?

X

 

 

따라서 점화식을 다음과 같이 수정해야 한다.

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

 

코드

---

import sys

n = int(sys.stdin.readline().strip())
wine = [int(sys.stdin.readline().strip()) for _ in range(n)]

result = 0

if n == 1 or n == 2:
    result = sum(wine)
    
else:
    dp = [0 for _ in range(n)]
    dp[0] = wine[0]
    dp[1] = wine[0] + wine[1]

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

    result = dp[n - 1]

print(result)