[DP] python 2156 포도주 시식

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

2156번: 포도주 시식

# 2023.02.07
import sys
input = sys.stdin.readline

# 포도주를 2잔 연속까지는 마실 수 있음, 될 수 있는 대로 많은 양의 포도주를 맛보아야 함
n = int(input())
grape = [int(input()) for _ in range(n)]
dp=[0]*(n)
dp[0] = grape[0]
if n==2:
    dp[1]=grape[0]+grape[1]
if n>2:
    dp[1] = grape[0]+grape[1]
    dp[2] = max(grape[0]+grape[1], grape[0]+grape[2], grape[1]+grape[2])
    for i in range(3, n):
        dp[i]=max(dp[i-1], dp[i-2]+grape[i], dp[i-3]+grape[i-1]+grape[i])
print(max(dp))

key point

"현재의 값을 기준으로 이전의 값이 무엇이 와야 할까"가 dp의 가장 중요한 요소인 것 같음

 

1. 현재 선택 X: dp[i-1]이 오면 됨(i-1이 무엇이 와도 상관없기 때문에 grape[i-1]의 값이 O or X 둘 다 상관이 없음

2. 현재 선택 O: 현재의 값을 선택을 했기 때문에 뒤에 무엇이 오는지가 상당히 중요 -> 연속으로 최대 2개 선택이 가능하기 때문

현재의 값을 선택하였다면 i-1은 선택을 하지 않는 경우, 선택하는 경우로 나눌 수 있음

2-1) dp[i-2]+선택X+선택O: i-1, i 순서

2-2) dp[i-3]+선택X+선택O+선택O: i-2, i-1, i 순서