[백준] 2156번: 포도주 시식 (가능한 모든 상황을 고려하는 DP)

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

---

import sys

sys.stdin = open("input.txt")

n = int(sys.stdin.readline().rstrip())

wine = []

for _ in range(n):
    wine.append(int(sys.stdin.readline().rstrip()))

dp = [0] * (n+1)

dp[0] = wine[0]
if n > 1:
    dp[1] = wine[0] + wine[1]
if n > 2:
    dp[2] = max(wine[0]+wine[1], wine[1]+wine[2], wine[0]+wine[2])

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

print(max(dp))

 

알고리즘 분류:

- 다이나믹 프로그래밍

 

Key Points:

DP 유형으로 자주 나오는 계단 건너기 문제와 비슷한 듯 다르다. 우선 dp[i]는 i번째 포도주까지 시도한 상황에서 마실 수 있는 최대의 포도주 양이다. 3잔을 연속으로 마실 수 없기 때문에 i번째 포도주를 마주한 상황에서 생길 수 있는 상황은 총 세 가지이다.

 

1. 전전까지의 포도주 최댓값 + 현재 포도주

2. 전전전까지의 포도주 최댓값 + 이전 포도주 + 현재 포도주

3. 전까지의 포도주 최댓값 (현재 포도주 버림)

 

이 세 가지 상황 중 최댓값을 취하면서 계속 진행하면 된다. 처음에는 이렇게 상황을 다 따지기 시작하면 결국 상황 별로 예외를 다 생각해야 하나... 했지만 이 세 가지 상황으로 모든 경우의 수가 커버된다.

 

여기서 중요한 건 1번 상황과 2번 상황을 보았을 때, 각각 전전 포도주, 전전전 포도주를 마셨는지 안 마셨는지 정확히 알 수는 없지만 일단 최댓값이 적혀있을테니, 연속된 3잔을 마시는 상황을 피하기 위해서 전전 포도주와 전전전 포도주를 마셨다고 가정한 상태로 진행한다는 것이다.

 

이게 사실 글로 적으면 이렇게 세 가지의 상황이 나온다는 걸 알기는 알겠는데 정작 머리로 생각하려고 하면 뒤죽박죽 꼬이기 시작하고, 예외 상황이 자꾸 생각나서 결국 길을 잃는다... DP 어렵다...