[백준] 2156 : 포도주 시식 python

 

세 잔을 연속해서 마실 수 없기 때문에

(마시는 걸 O, 마시지 않는 걸 X라고 했을 때)

OXO : dp[i-3]+dp[i-2]+arr[i]

XOO : arr[i-1]+arr[i]

이 두 가지 경우를 생각했는데 마지막잔을 마시지 않아도 된다는 점을 간과해서 문제가 풀리지 않았다.

 

OOX : dp[i-1] 인 경우도 구해서 세 가지 경우 중 최댓값인 걸 dp[i]에 저장하도록 해서 해결했다.

 

import sys
input = sys.stdin.readline
n=int(input())
arr = [int(input()) for _ in range(n)]
dp = [0]*n
dp[0] = arr[0]

if n>1:
    dp[1] = arr[0]+arr[1]
if n>2:
    dp[2] = max(dp[1], arr[0]+arr[2], arr[1]+arr[2])
for i in range(3,n):
    dp[i] = max(dp[i-3]+arr[i-1]+arr[i],dp[i-2]+arr[i],dp[i-1])
print(max(dp))