[백준] 2156번 : 포도주 시식 (Python)

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

 

n개의 포도주 잔과 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때,

가장 많은 양의 포도주를 마실 수 있게 구하는 문제.

import sys

input = sys.stdin.readline

N = int(input()) # 포도주 개수
wine = [0]*(N+1)
dp = [0]*(N+1)

# 포도주 입력받기
for i in range(1, N+1):
    
    wine[i] = (int(input())) # 입력받은 포도주를 추가


# 최대로 마실 수 있는 포도주의 양 출력
dp[1] = wine[1]

if(N >= 2):
    dp[2] = wine[1] + wine[2]

for i in range(3, N+1):

    # 1. 현재 잔 선택 x, 이전의 연속된 2잔
    wine1 = dp[i-1]

    # 2. 현재 먹는잔+이전의 잔 이렇게 연속된 2개 선택
    wine2 = dp[i-3]+wine[i]+wine[i-1]

    # 3. 현재 먹는잔+한칸 띄어 먹는 잔
    wine3 = dp[i-2]+wine[i]

    dp[i] = max(wine1, wine2, wine3) # 가장 최대가 되는 잔 선택
    

print(dp[N])

 

 

 

 

[문제풀이]

---

 

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

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

 

이 두개의 규칙에 따라 문제를 풀기 위한 점화식을 세워야 한다.

우선, 규칙에 따라 이 문제를 풀기 위한 방법은 이렇다.

 

 

 

이전에 구한 포도주의 최댓값들의 누적합에서, 포도주가 새로 들어올 경우엔 연속 세잔을 먹지 않고 최대로 먹는 경우는 이 세가지다.

이 규칙에 따라 포도주의 최댓값을 구하는 예시를 들어보자.

 

 

\

 

여기서 DP[i-1]의 최댓값은 3잔 연속 선택 불가로 8L와 9L가 들고 있는 잔 2개를 선택하는 경우다.

그래서 현재 잔을 선택하지 않고 이전의 잔을 선택하는 경우와, 현재 잔 -2 잔을 선택하지 않고 나머지 잔을 선택하는 경우, 그리고 현재 잔 바로 이전의 잔을 선택하지 않는 이 세가지 경우 중 최댓값을 선택하면 누적 최대 잔을 구할 수 있다.

 

이를 점화식으로 만들면 이렇게 된다.

# 1. 현재 잔 선택 x, 이전의 연속된 2잔
wine1 = dp[i-1]

# 2. 현재 먹는잔+이전의 잔 이렇게 연속된 2개 선택
wine2 = dp[i-3]+wine[i]+wine[i-1]

# 3. 현재 먹는잔+한칸 띄어 먹는 잔
wine3 = dp[i-2]+wine[i]

dp[i] = max(wine1, wine2, wine3) # 가장 최대가 되는 잔 선택

 

 

이 점화식을 이용해 문제의 누적 최대 포도주의 값을 구하면 마지막 N번째가 N잔의 포도주가 들어왔을 때 최대로 먹을 수 있는 값이다!