❓2156번 : 포도주 시식
〽️ 문제 요약
n개의 포도주 잔이 있을 때 다음 조건에 만족하도록 포도주를 선택해 마시는 경우 최대로 마실 수 있는 포도주의 양을 구하면 되는 문제
- 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
- 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.
🤨 접근법
수열에서 연속으로 3개의 부분 수열을 선택하지 못한다는 점에서 계단 오르기 문제와 닮아있다. 전체 문제를 전체 포도주 에서 마실 수 있는 최대의 양을 구하는 문제로 정의하고, 부분 문제를 i번째 포도주 까지 마실 수 있는 최대의 양을 구하는 문제로 정의하여 DP 방식으로 풀이하였다.
즉, DP 배열이 있을 때 DP[i]는 전체 포도주 중 i 번째 포도주까지 선택할 수 있는 경우 마실 수 있는 최대의 양을 구한 것이다.
연속으로 3잔을 마시지 못하기 때문에 DP[i]를 구하기 위해서 다음과 같이 두 방법으로 DP[i]까지 Tabulation이 진행된다. (p 배열은 각 포도주 잔의 양)
- dp[i-2] + p[i]
- i-2번째 잔을 마시고 i번째 잔을 마시게 되는 경우
- dp[i-3] + p[i-1] + p[i]
- i-3번째 잔과 i-1번째 잔을 마신 후 i번째 잔을 마시게 되는 경우
두 경우 중 더 큰 값을 dp[i]로 선택하면 될듯 하다. 아래와 같이 코드를 작성하게 된다.
for i in range(4, n+1):
dp.append(max(dp[i-2]+p[i], dp[i-3]+p[i-1]+p[i]))하지만 이렇게 dp 배열을 완성하면 문제는 틀리게 된다. 왜일까?
계단 오르기 문제에서는 위와 같은 방법으로 코드를 작성하면 정답이다. 그러나 이번 문제와 다른 점은 마지막 계단을 필수로 밟았어야 했다. 그렇기 때문에 dp[i]를 i번째 계단을 밟는 최대 합으로 부분문제를 정의하여 풀이하면 성립했다.
하지만 이번 문제는 마지막 잔을 마셔도 되고 안마셔도 된다. 헷갈리는 점은 마지막 잔까지 마시는 것을 고려하면 결과적으로 더 많이 마실 수 있게 되지 않나? 라고 자칫 생각할 수 있는데, 마지막 잔을 마심으로써 dp[i]가 최대가 아니게 되는 경우가 발생한다.
우리가 관리하는 dp는 i번째 포도주 잔까지 고려했을 때 최대를 고려해야 낮은 인덱스 부터 Tabulation을 진행하는 문제의 특성상 문제가 발생하지 않는다. 그렇기 때문에 i번째 포도주 잔을 마시지 않을 때 최대가 되는 경우를 고려하기 위해 max 연산에 다음과 같이 dp[i-1]항을 같이 넣어 비교해 최대를 dp[i]로 해야 한다.
for i in range(4, n+1):
dp.append(max(dp[i-2]+p[i], dp[i-3]+p[i-1]+p[i], dp[i-1]))🔡 코드
import sys
input = sys.stdin.readline
n = int(input())
p = [0]+[int(input()) for _ in range(1, n+1)]
dp = [0]
if n >= 1:
dp.append(p[1])
if n >= 2:
dp.append(p[1]+p[2])
if n >= 3:
dp.append(max(p[1]+p[2], p[2]+p[3], p[1]+p[3]))
for i in range(4, n+1):
dp.append(max(dp[i-3]+p[i-1]+p[i], dp[i-2]+p[i], dp[i-1]))
print(dp[n])n=3 까지는 기저항으로, 인덱스 에러를 방지하기 위해 n ≥ 1, n ≥ 2, n ≥ 3 인지 검사하여 적절하게 dp 배열의 기저를 만들 수 있도록 했다.
📚 고찰
문제를 보자마자 어..? 저번에 풀었던 문제와 똑같은 거 아닌가? 하면서 거침 없이 코드를 작성했지만 가장 중요한 차이점에 막히고 말았다. i번째 항을 꼭 포함해야 하는 경우와 포함하지 않아도 되는 경우를 고려해야 한다는 것을 시행착오를 겪을 때 까지 생각하지 못했다.
그래도 DP의 유형들을 차근차근 알아가고 있다는 생각을 드디어 이번 문제에서 조금이나마 하게 되었다.
