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

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

2156번: 포도주 시식

생각보다 까다로웠던 dp 문제이다. (사실 dp문제는 다 까다롭지만,,)

dp[1], dp[2], dp[3]까지는 손쉽게 생각할 수 있다.

dp[i]가 의미하는 바는 i번째 와인까지 마셨을 때 최대로 마실 수 있는 와인의 양이다.

 

1. 전전 와인 먹지 않고 전 와인과, 현재 와인 마시기 + 전전전 와인까지의 최댓값

2. 전 와인 먹지 않고 현재 와인 마시기 + 전전 와인까지의 최댓값

3. 전 와인까지 먹었을 때 최댓값

 

dp[4] = max(1번째 와인까지 먹었을 때 최댓값 + 3번째 와인 + 4번째 와인, 2번째 와인까지 먹었을 때 최댓값 + 4번째 와인, 3번째 와인까지 먹었을 때 최댓값=현재 와인 먹지 않기) 를 이용하면 점화식을 세울 수 있다. 

 

import sys
#sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())

wine = [0] + [int(input()) for _ in range(n)]
dp = [0 for _ in range(10001)] # i번쨰 와인까지 마셨을 때 마실 수 있는 최대치

dp[1] = wine[1]

if n>=2 :
  dp[2] = wine[1] + wine[2]
  if n>=3 :
    dp[3] = max(wine[1] + wine[3], wine[2] + wine[3], wine[1] + wine[2])
    if n>=4:
      for i in range(4,n+1):
        dp[i] = max(wine[i] + wine[i-1] + dp[i-3], dp[i-2]+wine[i], dp[i-1])
    
print(dp[n])