[백준] 2156 포도주 시식

---

일렬로 놓여 있는 포도주를 마실 수 있는 최대의 양을 구하는 문제 DP로 풀이가 가능하다. 규칙은 아래와 같다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

위 규칙에 따르면 포도주를 마실 수 없는 경우가 나타나는데 이를 3가지로 나눌 수 있다.

 

1. 현재 포도주를 마시지 않는다.

2. 이전의 포도주를 마시지 않는다.

3. 2번째 이전의 포도주를 마시지 않는다.

 

이 세 가지 경우를 각각 적어도 하나만 만족한다면 위 2가지 규칙을 만족한다.

 

소스 코드

파이썬

from sys import stdin
readline = stdin.readline

N = int(readline())
wines = [int(readline()) for _ in range(N)]

def dp():
    d = [0, wines[0], wines[0]]
    for i in range(1, N):
        # 0: 현재 포도주를 마시지 않는다
        # 1: 첫 번째 이전 포도주를 마시지 않는다
        # 2: 두 번째 이전 포도주를 마시지 않는다
        d = [max(d), d[0]+wines[i], d[1]+wines[i]] 

    return max(d)

print(dp())