백준 2156번 파이썬 문제풀이(DP - 포도주 시식) - 자세한 설명

---

(사실 해당 문제가 30분 내에 DP라는 것도 생각하기 힘든데 점화식까지 구할려고 하니 머리가 터지는 줄 알았다... 답을 볼 수 밖에 없었지만 생각보다 이해하기는 어렵지 않았다.)

 

6잔의 포도주가 있다.( 6, 10, 13, 9, 8, 1) 이 있는데 점화식을 구할때는 바로바로 dp[0] 부터 생각을 해보는 것이 좋다. dp[0] 은 당연히 0이고 dp[1] 일때 최댓값은 와인이 1개 밖에 없으므로 wine[1] 이 될것이다.(wine 인덱스가 1부터 시작한다고 생각) dp[2] = wine[1]+wine[2] 까지는 불변이다.(wine의 양이 음수일 수 없으므로) 그럼 여기서 우리는 dp[3] 부터는 식으로 찾아야한다는 말이 된다. 어떻게 생각할 수 있을까?

 

우선 dp[3] 즉, 와인이 3개있을 때 최대로 마실 수 있는 경우의수를 생각해보면 된다. 우선 현재 3번째 와인을 마실 경우 3개연속은 마실 수 없기에

1. 2번째 와인과 3번째 와인을 함께 마시는 경우

2. 3번째 와인만 마시는 경우

3. 3번째 와인을 마시지 않고 직전와인까지만 마시는 경우(즉, 3번째 와인을 마시지 않는 경우)

이렇게 3가지 경우가 나온다.

점화식을 풀어 보겠다.(여기서 dp[i] 는 i번째 까지의 최대 와인 양이다.)

1. dp[3] = dp[0] + wine[2] + wine[3] 

2. dp[3] = dp[1] + wine[3]

3. dp[3] = dp[2]

이식을 이해 할 수 있어야 한다. 왜 1번 식이 dp[1] + wine[2] + wine[3] 이 아닐까? dp[1]이 되어버리면 dp[1] = wine[1]이 저장되어있기 때문이다. 그럼 3잔 연속을 선택한 꼴이 되어버리지 않는가?

마찬가지로 2번째도 동일하다. dp[2] + wine[3]이 아닌 이유는 dp[2] 에는 이미 wine1,2 가 선택이 되어있다. 즉, dp[1] 에는 1잔을 골랐을 때의 최대값이 저장되어 있기 때문에 거기에 wine[3]를 골라주면 조건에 위배되지 않게 와인을 고를 수 있다는 것이다.

마지막 와인을 선택하지 않는 이유도 왜 추가해야 하는지 의아할 수 있다. wine[3]번째를 고르지 않고 즉, wine[1],wine[2] 만 고른것이(=dp[2]) 다른 조건 wine[2] + wine[3] + dp[0] , dp[1]+wine[3] 보다 클 수도 있다. 그렇기 때문에 해당 조건이 들어가는 것이다.

 

따라서 완성된 점화식은 

dp[i] = dp[i-3] + wine[i-1] + wine[i] 

dp[i] = dp[i-2] + wine[i]

dp[i] = dp[i-1] 

이 된다.

 

코드는 다음과 같다.

import sys

input = sys.stdin.readline

N = int(input())
wine = [0]
for _ in range(N):
    wine.append(int(input()))

dp = [0] * (N + 1)

dp[1] = wine[1]
if N >= 2:  # N이 1보다 클때만 dp[2]값을 처리하도록 예외처리
    dp[2] = wine[1] + wine[2]

for i in range(3, N + 1):
    dp[i] = max(dp[i - 1], dp[i - 2] + wine[i], dp[i - 3] + wine[i - 1] + wine[i])

print(dp[N])