행복한 삶을 찾아서

기초적인 DP 문제이니 점화식을 잘 짜보자.

지금까지 마셔왔던 최대 양과 잔에 든 양을 바탕으로 n번째 잔에서 마실 수 있는 최대 양을 계산하는 것이 관건. 어떤 것을 고르고 어떤 것을 스킵할지에 주목. 반복문 초기에 0, 1, 2 케이스까지 실수없이 계획 세우기.

n = int(input())
wine_list = []

for a in range(n):
	wine_list.append(int(input()))

max_list = [0]*n

'''
n 번째 max_list 값은
1. max_list[n-1] -> n을 skip
2. n + max_list[n-2] -> n-1을 skip
3. n + n-1 + max_list[n-3] -> n-2를 skip
1,2,3 중 max값을 가져간다

itr==2 인 경우는?
1. max_list[itr-1] -> 2를 skip
2. wine_list[2]+wine_list[0] -> 1을 skip
3. wine_list[2]+wine_list[1] -> 0을 skip
'''

for itr in range(n):
	if itr == 0:
		max_list[itr] = wine_list[itr]
	elif itr == 1:
		max_list[itr] = max_list[itr-1] + wine_list[itr]
	elif itr == 2:
		max_list[itr] = max(max_list[itr-1], wine_list[itr]+wine_list[itr-2], wine_list[itr]+wine_list[itr-1])
	else:
		max_list[itr] = max(max_list[itr-1], wine_list[itr] + max_list[itr-2], wine_list[itr]+wine_list[itr-1]+max_list[itr-3])

print(max_list[n-1])