[BOJ/python] 2156: 포도주 시식

문제

✔️ silver 1

문제 흐름

전에 풀었던 계단 문제가 떠오르는 문제였다.

앞에 마셨던 최대 포도주 양을 통해 현재까지 마실 수 있는 최대 포도주의 양도 계산할 수 있으므로 DP임을 알 수 있다.

memo[i]를 i번째 잔을 마신다고 가정할 때 맛볼 수 있는 최대 포도주의 양으로 설정했다.
중요한건 i가 3번째 잔이 되지 않게 해주는것인데, 이를 고려하며 생각하면 memo[i]를 구하는 방법에는 세가지가 있다.

위 그림들에서 파란색은 그 잔에 있는 포도주 양을 나타내고, 하늘색은 그 잔까지의 memo[i](i번째 잔까지의 최대 포도주 양)을 나타낸다.
현재보다 3개 전 잔까지 있어야 이후 위 방법들을 이용해 반복적으로 memo를 구할 수 있다.
따라서 n이 0, 1, 2인 케이스를 초기값으로 잡았다.
위의 세 경우를 비교해서 가장 큰 경우를 memo[i]로 넣어주면 되겠다!

나는 세번째 방법을 놓쳐서 조금 헤맸었는데, 나같이 세번째 케이스를 놓치고 왜 필요한지 모르겠는 분들을 위해 반례 하나 남겨본다!

# input
6
3
3
1
1
3
3

# output
12

코드

# 포도주 시식

import sys
input = sys.stdin.readline

def dp (lst: list):
    n = len(lst)
    if n == 1:
        return lst[0]
    elif n == 2:
        return lst[0] + lst[1]

    # memo[i]: i번째 잔을 마신다고 가정할 때 맛볼수 있는 최대 포도주 양
    memo = [0 for i in range(n)]
    memo[0] = lst[0]
    memo[1] = lst[0] + lst[1]
    memo[2] = max(lst[0] + lst[1], lst[1] + lst[2], lst[0] + lst[2])

    for i in range(3, n):
        val_1 = lst[i-1] + memo[i - 3]
        val_2 = memo[i - 2]
        val_3 = lst[i-1] + memo[i - 4]
        memo[i] = max(val_1, val_2, val_3) + lst[i]

    # print(* memo)
    return max(memo)

if __name__ == "__main__":
    n = int(input())

    wine = []
    for i in range(n):
        w = int(input())
        wine.append(w)
    
    result = dp(wine)
    print(result)