새싹프로그래머의 이야기

https://www.acmicpc.net/problem/2156

문제: 포도주 잔이 일렬로 놓여 있을 때, 3잔 연속으로 마시지 않는 경우 중 제일 많이먹는 경우를 구하는 문제

풀이 방법: DP

풀이 코드:

import sys

n = int(sys.stdin.readline())
arr = [0]*(n+1)
dp = [0] *(n+1)
for i in range(1,n+1):
    arr[i] = int(sys.stdin.readline())

if n == 1:
    print(arr[1])

else:
    dp[1] = arr[1]
    dp[2] = arr[1] + arr[2]

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

    print(max(dp))