[백준 2156 파이썬] 포도주 시식

백준 2156번 python 포도주 시식문제 DP

 

3잔을 연속해서 마시지 않고 최대한 많은 와인을 마셔야하는 문제

3개의 case로 나누었다.

와인이 4잔 있을 경우

 

 

case1: 현재의 와인(와인4)을 마시고 이전의 와인(와인2)를 마시지 않고 그 전의 마실 수 있는 와인의 최대치를 마심

case2: 현재의 와인(와인4)과 이전의 와인(와인3)를 마시고 와인2를 못마시는경우

case3: 와인2과 와인3를 마셔 현재의 와인4를 마시지 못하는경우

 

case1: wine4 + (wine1+wine2)

case2: wine4 + wine3 + (wine1)

case3: wine2 + wine3

 

이런식이 될것임

n = int(input())
wine = [0]
dp = [0]
[wine.append(int(input())) for _ in range(n)]
dp.append(wine[1])

if n > 1 :
    dp.append(wine[1]+wine[2])

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

print(dp[n])