풀이
문제
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 |