백준 2156번 : 포도주 시식 (Python)

문제 : www.acmicpc.net/problem/2156

2156번: 포도주 시식

 

풀이

A에 포도주 양을 입력받는다.

dp에 해당 위치 포도주를 마셨을 경우의 최대 양을 저장한다.

연속 3잔을 마실 수 없으므로 가능한 경우는

① 현재 포도주 + 현재-2 까지의 dp중 최대값  (1개 연속)

② 현재 포도주 + 현재-1 포도주 + 현재-3 까지의 dp중 최대값  (2개 연속)

이렇게 두가지이다.

최종적으로 가장 큰 dp값을 출력한다.

 

n = int(input())
A = []
for i in range(n):
    A.append(int(input()))

dp = [0 for _ in range(n)]

dp[0] = A[0]
if n>1:
    dp[1] = A[0]+A[1]
if n>2:
    dp[2] = max(A[2]+A[0], A[2]+A[1])

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

print(max(dp))