[백준] 2156 포도주 시식, python

www.acmicpc.net/problem/2156

2156번: 포도주 시식

n = int(input())
wine = [0] + [int(input()) for _ in range(n)]
dp = [0] * (n + 1)
# 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.
# 최대 두잔 연속
dp[1] = wine[1]
if n >= 2:
    dp[2] = max(wine[1]+wine[2], dp[0] + wine[2])
    for i in range(3, n + 1):
        dp[i] = max(dp[i - 2] + wine[i], dp[i - 3] + wine[i - 1] + wine[i])
        dp[i] = max(dp[i - 1], dp[i])
print(dp[-1])

예전에 풀어봤던 계단오르기와 비슷한 문제이다.

근데 다시보니 어떻게 풀어야할지 감이 안잡혔다. 그래서 얘도 구글링을 했다.

연속으로 마신 이후 한번 쉬어야하는 경우를 생각해서 점화식을 구해야하는데, 그 한번 쉰 경우가 언제인지를 생각하면 조금 편하다

연속으로 세번을 마실수 없으므로 최대 두번까지 마실수 있으므로 이전에 안마신경우와 전전(두번 건너 뛴 경우)에 쉬었는지를 판단하면 된다. (여기까지가 계단오르기와 같은 알고리즘이다.)

이 문제가 계단오르기와 다른점은 꼭 마시지 않아도 되므로 두 번 이상 안마실수도 있다는 것이다.

예를들어 100 400 5 6 7 100 으로 되어있으면 100+400+7+100 으로 마시는게 최대값이다

따라서 이전 값과 비교하면서 더 큰값이 뭔지 한번더 비교해야 성공할수 있다.

---

그렇다면 최대 세번까지 마실수 있는 경우는 세개를 비교하면 되겠지?

dp 너무 어렵다