풀이
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규
www.acmicpc.net
문제
dp[i]를 i 번째 와인을 골랐을 때 마실 수 있는 와인 양의 최대값으로 한다.3 잔 연속으로 마실 수 없다는 점에 착안하여 점화식을 세우되, i-1 번째 와인을 마시면 i-4 번째 와인을 마시는 경우와 i-3 번째 와인을 마시는 경우 두가지가 존재한다는 점을 주의하자.
N = int(input())
wine = [0]*10001
for i in range(1,N+1):
wine[i] = int(input())
dp = [0]*10001
dp[1] = wine[1]
dp[2] = wine[1]+wine[2]
dp[3] = max(wine[1],wine[2]) + wine[3]
for i in range(4,N+1):
dp[i] = max(wine[i-1]+dp[i-4],wine[i-1]+dp[i-3],dp[i-2]) + wine[i]
print(max(dp[N],dp[N-1]))'PS > 백준' 카테고리의 다른 글
| 11054번 - 가장 긴 바이토닉 부분 수열 (0) | 2022.11.04 |
|---|---|
| 11053번 - 가장 긴 증가하는 부분 수열 (0) | 2022.11.04 |
| 10844번 - 쉬운 계단 수 (1) | 2022.10.22 |
| 1463번 - 1로 만들기 (0) | 2022.10.22 |
| 2579번 - 계단 오르기 (0) | 2022.10.21 |