최대로 마실 수 있는 포도주의 양 구하기.
입력 | 출력 |
---|---|
6 6 10 13 9 8 1 | 33 |
: dp로 푼다. 계단 오르기 문제와 마찬가지로 연속 세개의 포도주를 마실 수 없으므로
현재 포도주를 마시지 않는 경우도 고려해야한다.
계단 오르기 문제에서는 한 번에 한 계단 or 두 계단까지 올라갈 수 있었지만, 포도주는 그러한 조건이 없으므로 꼭 안마셔도 된다.
ex. [100, 400, 5, 6, 7, 100] 에서 100+400+7+100으로 마시는 것이 최댓값.
n = int(input())
wine = []
for _ in range(n):
wine.append(int(input()))
dp = []
dp.append(wine[0])
if n == 1:
print(dp[0])
exit()
dp.append(wine[0]+wine[1])
if n==2:
print(dp[1])
exit()
dp.append(max(dp[1], wine[0]+wine[2], wine[1]+wine[2]))
for i in range(3, n):
dp.append(max(dp[i-1], wine[i]+wine[i-1]+dp[i-3], wine[i]+dp[i-2]))
print(max(dp))