2156번 - 포도주 시식(Python)

풀이

dp를 이용해 조건에 부합하는 최댓값을 저장한다.

 

i번째 까지의 포도주의 합이 최대가 될 수 있는 경우는 다음과 같다.

 

1) i번째 포도주를 마시지 않고, i-1번째 까지의 최댓값

2) i번째 포도주를 마시고, i-2번째 까지의 최댓값

3) i번째 포도주와 i-1번째 포도주를 마시고, i-3번째 까지의 최댓값

 

이를 이용하여 dp에 최댓값을 저장한다.

 

n이 3보다 작을 경우 위 식이 적용되지 않으므로 예외 처리한다.

코드

import sys


input = sys.stdin.readline

n = int(input())
wines = [int(input()) for _ in range(n)]

dp = [-1 for _ in range(n)]
if n == 1:
    print(wines[0])
elif n == 2:
    print(wines[0] + wines[1])
else:
    dp[0] = wines[0]
    dp[1] = wines[0] + wines[1]
    dp[2] = max(dp[1], wines[2] + wines[1], wines[2] + wines[0])

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

    print(dp[-1])