백준 2156 포도주 시식 - 파이썬

문제.

 

풀이.

풀이 방법이 DP문제의 계단 오르기랑 많이 유사하다.

마지막을 번호를 기준으로 구해야하는 경우의 수는 총 3가지다.

예를 들어

1 2 3 4 가 있다면 마지막 4번을 기준으로 나올 수 있는 경우의 수는 (1, 2, 4), (1, 3, 4), (2, 3)

즉 마지막잔을 마신다면 그 이전 잔을 마시냐 안마시냐와 마지막잔을 안마시는 경우 이렇게 총 3가지로 나뉘어서 소스코드를 작성하면 된다.

 

소스코드.

import sys

n = int(sys.stdin.readline())
drink = [0] * 10000
dp = [0] * 10000
for i in range(n):
    drink[i] = int(sys.stdin.readline())

dp[0] = drink[0]
dp[1] = drink[0] + drink[1]
dp[2] = max(dp[0] + drink[2], dp[1], drink[1] + drink[2]) # 마지막 잔을 마시고 이전 잔을 안먹을 경우, 마지막잔을 안마실 경우, 마지막 잔과 이전 잔을 마실경우

for i in range(3, n):
    dp[i] = max(dp[i-2] + drink[i], dp[i-1], dp[i-3] + drink[i-1] + drink[i]) # 마지막 잔을 마시고 이전 잔을 안먹을 경우, 마지막잔을 안마실 경우, 마지막 잔과 이전 잔을 마실경우
print(dp[n-1])