[Dynamic Programming] 포도주 시식

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

Description

포도주 잔이 일렬로 놓여 있고, 각각의 잔에 들어 있는 포도주의 양이 주어진다. 포도주를 한 개씩 골라서 먹는데, 연속된 세 잔을 모두 마실 수는 없다. 최대로 마실 수 있는 포도주의 양을 구하라.

Idea

n개의 포도주가 있다고 할 때, i : 0~n 마다 zero, one, two를 update한다.

zero : i번째 와인을 안 먹을 때의 최고 점수.

one : i번째 와인을 먹고 i-1번째 와인은 안 먹을 때의 최고 점수.

two : i번째 와인과 i-1번째 와인 모두 먹을 때의 최고 점수.

i번째 와인의 점수를 $ s $라 하면 아래와 같은 식이 성립한다.

$ zero_i = max(zero_{i-1}, one_{i-1}, two_{i-1}) $

$ one_i = zero_{i-1} + s $

$ two_i = one_{i-1} + s $

Code

scores = [int(input()) for _ in range(int(input()))]
# zero : highest score when the one does not choice the last wine
# one : highest score when the one choice the last wine, but not the previous one
# two : highest score when the one choice the last wine and the previous one
# define initial conditions
zero, one, two = 0, scores[0], 0

# starting from index 1, iterate through last wine
for score in scores[1:]:
	zero, one, two = max(zero, one, two), zero + score, one + score

print(max(zero, one, two))