[Python] 백준 2156번: 포도주 시식 풀이

 

소스코드

n = int(input())
wine = []
dp = [[0] * 3 for _ in range(n)]
for i in range(n):
    wine.append(int(input()))
dp[0][1] = wine[0]
for i in range(1,n):
    dp[i][0] = max(dp[i-1])
    dp[i][1] = dp[i-1][0] + wine[i]
    dp[i][2] = dp[i-1][1] + wine[i]
print(max(dp[n-1]))

 

n 이 1일때를 고려해주지 않아 계속 런타임 에러가 난 문제... 휴!

 

연속으로 와인 3잔을 먹지 못하는 것을 힌트로 문제를 풀어나가면 된다.

dp[i][j] 는 i번째 와인을 먹을 때, 최대로 마실 수 있는 포도주의 양을 저장한 것이다. 

i는 0부터 n-1까지이며, j는 0,1,2 이다.

예제 입력처럼 와인이 6  10 13  9   8  1 로 나열되어 있다고 하자.

           인덱스        (0) (1) (2) (3) (4) (5)

dp[3][0] 은 3번째 와인을 마시지 않을 때의 최댓값 -> max(dp[i-1]) = dp[2][2] 일 것이다. -> 10 + 13 = 23 (2번째 와인에서 연속으로 2잔을 먹을 때)

dp[3][1] 은 3번째 와인을 연속 첫 잔으로 먹을 때 -> dp[2][0] + wine[3] = 16 + 9 = 25

dp[3][2] 는 3번째 와인을 연속 두 잔으로 먹을 때 -> dp[2][1] + wine[3] = 19 + 9 = 28

따라서 dp[3] 즉, 3번째 와인까지 최대로 마실 수 있는 포도주는 6, 13, 9 이다.