🧩 문제 : 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])
🎁 성공!
'알고리즘' 카테고리의 다른 글
[BOJ / Python] 1484 다이어트 (0) | 2023.01.30 |
---|---|
[BOJ / Python] 1325 효율적인 해킹 (1) | 2023.01.24 |
다이나믹 프로그래밍 (0) | 2023.01.20 |
[BOJ / Python] 내일 할거야 (0) | 2023.01.16 |
정렬 알고리즘 #선택 정렬/삽입정렬/퀵 정렬/계수 정렬 (0) | 2023.01.14 |