백준 알고리즘 2156번 포도주 시식(python)

기본적인 다이나믹 프로그래밍 문제이다. 현재 포도주를 마시지 않는 경우, 앞에 포도주를 마시고 현재 포도주를

마시는 경우, 앞에 포도주를 마시지 않고 현재 포도주를 마시는 경우로 총 세 가지를 고려해주면 된다.

-> dp[i] = max(dp[i-1], dp[i-3]+li[i-1]+li[i], dp[i-2]+li[i])

n = int(input())
li = [0] + [int(input()) for _ in range(n)]
dp = [0]*(n+1)
dp[1] = li[1]
if n > 1:
    dp[2] = li[1] + li[2]
for i in range(3, n+1):
    dp[i] = max(dp[i-1], dp[i-3]+li[i-1]+li[i], dp[i-2]+li[i])
print(max(dp))