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

N = int(input())
wine = [0]
maxi = [0]*(N+1)
for i in range(1, N+1):
    wine.append(int(input()))
    if i < 3:
        maxi[i] = sum(wine)
    else:
        target = []
        target.append(maxi[i-3]+wine[i-1]+wine[i])
        target.append(maxi[i-2]+wine[i])
        target.append(maxi[i-1])
        maxi[i] = max(target)
print(maxi[-1])

 

다이나믹 프로그래밍 문제다.

처음에 DFS로 풀었는데 시간초과가 떠서 다시 풀었다.

포도주가 1잔 또는 2잔이 있을 때에는 그냥 모두 다 마시면 된다.

하지만 3잔째 부터는 선택을 해야 한다.

선택에는 3가지 종류가 있다.

예를들어 5잔이 있다고 가정한다면

1. 2번째 잔까지의 최댓값 + 3번째 잔은 마시지 않고 + 4번째와 5번째 잔을 마신다.

2. 3번째 잔까지의 최댓값 + 4번째 잔은 마시지 않고 + 5번째 잔을 마신다.

3. 4번째 잔까지의 최댓값 + 5번째 잔을 마시지 않는다.

 

이 중에 max를 고르면 된다.

그리고 이 과정을 3번째 잔부터 n번째 잔까지 결과를 기록하며 나아간다.