[백준 - Python] 2156. 포도주 시식 (DP)

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

2156번: 포도주 시식

 

코드

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

dp = [0] * n

for i in range(n):
    if i == 0:
        dp[0] = wine[0]
    elif i == 1:
        dp[1] = wine[0] + wine[1]
    else:
        # 마지막 잔을 마시지 않았을 때, 마지막 잔을 마시고 전 잔을 안 마셨을 때, 마지막 잔을 마시고 전 잔도 마셨을 때
        # 계단 오르기 문제와 유사한데, 마지막 잔을 꼭 마시지 않아도 되는 점만 다르다
        dp[i] = max(dp[i-1], dp[i-2] + wine[i], dp[i-3] + wine[i-1] + wine[i])

print(dp[n-1])

 

계단 오르기 문제랑 같이 보면 좋을 문제다.

 

문제를 읽으면서 연속으로 놓여 있는 3잔을 모두 마실 수는 없다는 조건을 읽고

바로 계단 오르기 문제를 떠올렸다

 

그때 학습했던 풀이를 떠올리면서 쉽게 풀리겠구나 했는데,

자꾸 오답 처리가 됐다

 

이 문제는 게단 오르기 문제랑 다르게

마지막 잔을 꼭 마시지 않아도 된다는 점을 간과했던 점이 오답의 원인이었다.

 

코드에서 점화식 부분을 확인해보면,

첫 번째 인자는 마지막 잔을 마시지 않았을 경우이고

두 번째 인자는 마지막 잔을 마시고 전 잔을 안 마셨을 때이고

세 번재 인자는 마지막 잔을 마시고 전 잔도 마셨을 때이다

 

첫 번째 인자로 마지막 잔을 마시지 않은 경우를 추가해주니까 통과가 되었다 !