2156번: 포도주 시식 / sliver 1 / DP

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

2156번: 포도주 시식

'''
2156번: 포도주 시식 / sliver 1 / DP
'''
import sys

input = sys.stdin.readline

# 1. 입력 받기 n, wine
n = int(input())
wine = [0]
for _ in range(n):
    wine.append(int(input()))
# 2. DP 알고리즘
dp = [0 for _ in range(n + 1)]
dp[1] = wine[1]
if n > 1:
    dp[2] = wine[1] + wine[2]
for i in range(3, n + 1):
    dp[i] = max(dp[i - 1], dp[i - 3] + wine[i - 1] + wine[i],
                dp[i - 2] + wine[i])
# 3. 출력 
print(dp[n])

 

# 1. 입력 받기 

n, wine

---

# 2. DP 알고리즘

- 정해진 규칙을 찾는게 핵심인 문제!

- 조건 : 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

 

dp[i] 는 1번~i번까지의 포도 주 마신 최댓 값

1. dp[i-1] 

2. dp[i-3] + wine[i-1] + wine[i] 

3. dp[i-2] + wine[i]

 

예시

i = 4이면,

1. dp[3] (1번~3번까지 최댓값) 이거나

2. dp[1](1번~1번까지 최댓값) + wine[3] + wine[4]

3. dp[2](1번~2번까지 최댓값) + wine[4] 

---

# 3. 출력 

dp[n] (1번~n번까지 최댓값) 출력