[BOJ / Python] 2156 포도주 시식

🧩 문제 : 2156번 포도주 시식

👩🏻‍💻 문제 정리 

테이블에 포도주가 잔이 담긴 잔이 순서대로 n개 있다. 

각 잔마다 포도주의 양이 다르다. 이때 가장 가장 많이 마실 수 있는 포도주의 양을 구하는 문제이다. 

 

위 예시를 보면, 6개의 잔이 있고 각각 포도주가 6, 10 , 13, 9, 8, 1만큼 담겨있다. 

이 때 첫번째 잔, 두 번째 잔, 네 번째 잔, 다섯 번째 잔을 선택할 때 포도주를 가장 많이 마실 수 있다. 

 

💪🏻 해결 방법 

1️⃣ DP 이용하기 

1. 테이블 정의하기 

2. 점화식 찾기

연속으로 세잔을 마실 수 없음을 이용해 다음과 같이 점화식을 작성하였다.

 

3. 초기값 정하기 

 

정답 코드 

import sys
input=sys.stdin.readline

n = int(input()) # 잔의 수
wine = [0] * 10001 # 포도주의 양
d = [0] * 10001

for i in range(1, n+1):
    wine[i] = int(input()) # 포도주의 양 입력


# d[i] = i번째 잔까지의 포도주 양
d[1] = wine[1]
d[2] = wine[1] + wine[2]

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

print(d[n])

 

🎁 성공!