[Python] 백준 2156 포도주 시식

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

2156번: 포도주 시식

코드 작성

n = int(input())
dp = [0] * 10001
w = [0] * 10001
for i in range(1, n+1):
    w[i] = int(input())
dp[1] = w[1]
dp[2] = w[1] + w[2]

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

코드 풀이

#0.
다이나믹 프로그래밍 문제를 풀면서 그 원리를 이해하는데 가장 도움이 됐던 문제 중 하나이다.

#1. 문제 이해
와인의 양 w를 입력받고, dp테이블을 0으로 10001개 세팅한다. n = 5라고 가정하고 포도잔 A, B, C, D, E 가 있다고 예를 들면, 5번째 포도잔을 마시는 방법은 3가지가 있다.
(B, D, E), (B, C, E), (A, C, D)

이때를 각각 순서대로
B를 먹고 C를 먹지 않는 경우 dp[i-3]
C를 먹고 D를 먹지 않는 경우 dp[i-2]
D를 먹고 E를 먹지 않는 경우 dp[i-1]

즉, 중복되는 경우의 수를 제외하면
(B, D, E), (C, E), (D)
이렇게 될 것이며,
각각 dp[i-3], dp[i-2], dp[i-1] 다음에 새로운 입력값 w을 마시는 경우가 되므로 종합하면

(B, D, E) : dp[i-3] + w[i-1] + w[i]
(C, E) : dp[i-2] + w[i]
(D) : dp[i-1]

이렇게 나타낼 수 있으며 점화식은
dp[i] = max(dp[i-1], dp[i-2] + w[i], dp[i-3] + w[i] + w[i-1])
로 나타낼 수 있다.

#2. 초기값
dp[1] = w[1]
dp[2] = w[1] + w[2]