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

문제

https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

코드

n = int(input())
juice = [int(input()) for _ in range(n)] + [0]
    
dp = [0] * (n+2)
dp[1] = juice[0]
dp[2] = dp[1] + juice[1]

if n >= 3:
    for i in range(3, n+1):
        dp[i] = max(juice[i-1]+dp[i-2], juice[i-2] + juice[i-1] + dp[i-3], dp[i-1])

print(dp[n])

설명

점화식을 세우는 게 가장 중요한 문제였다.

우선 1, 2번까지 최대로 마실 수 있는 양은 모두 마시는 경우이므로,
모두 마신 값을 지정해 준다.

3번의 경우 (1,3) (2,3) 2가지 경우의 수가 있는데 이 중에 최대치를 선택한다.
이는 점화식에서 선택해도 같으므로 한 번에 진행한다.
(안마시는 경우가 없음)

4번부터는 3가지 경우의 수가 존재한다.
1. 1,2,4
2. 1,3,4
3. 2,3
이렇게 3가지 수가 있는데, 1번과 2번은 직관적으로 알 수 있으니 넘어가고
3번의 경우는 4번 잔을 마시지 않는 경우이다.
3잔을 연달아 마실 수 없으므로 이 경우도 생각을 해주어야 한다.

따라서 3가지 경우 중 최대치인 경우를 지정해 주면 된다.

그리고 이 문제의 경우 인덱스 에러로 많이 고생했는데,
n이 1인 경우,
와인의 리스트를 n의 개수로만 지정하면 dp[2]의 juice[1]이 없는 수로 취급된다.

따라서 리스트의 뒤에 [0]을 하나 추가해주자.