[BOJ 2156] 포도주 시식(Python)

문제링크

포도주 시식

풀이 전 계획 및 생각

연속으로 놓여 있는 3잔을 모두 마실 수 없는 조건이 중요하다고 생각했다.
k번째의 포도주를 마실지 말지를 고려할 때 위의 조건을 감안했을 때 아래의 3가지를 고려하고 그 중 가장 큰 값을 만드는 경우를 선택하면 된다는 생각을 했다.
1. k-2번째 포도주까지의 최댓값과 k-1번째를 마시지않고, k번째를 마시는 경우
2. k번째 포도주를 마시지않는 경우(k-1번째 포도주까지 마신 경우를 그대로 가져옴)
3. k-3번째 포도주까지 마시고, k-2번째 포도주를 건너뛴 다음, k,k-1번째 포도주를 마시는 경우
이렇게 고려하면 그 어떤 경우에도 연속으로 놓여있는 3잔을 모두 마실 수 없다.

풀이

import sys
wine = [0]*10010
dp = [0]*10010

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

for i in range(1,n+1):
    wine[i] = int(sys.stdin.readline())

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

풀이하면서 막혔던 점과 고민했던 점

식을 만드는게 어려웠다. 일단 가능한 모든 경우를 구하는 방법을 생각해본 다음, 주어진 조건에 따라서 경우의 수를 차근차근 나눠서 해결할 수 있었다.

풀이 후 알게된 개념과 소감

DP를 풀 때, 막히면 근본이되는 완전탐색부터 시작해봐야겠다는 생각을 했다.