BOJ 2156번

DP 문제입니다.

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

2156번: 포도주 시식

점화식을 잘 만드는게 중요하였습니다.

dp1, dp2, dp3이라는 변수를 만들어 놓고

for문을 돌면서 podojoo_list에서 다음 값을 계속해서 가져와서 max()를 가지고 가장 큰 값을 dp4에 담고 

dp4 -> dp3

dp3 -> dp2

dp2 -> dp1

와 같이 dp1,2,3을 업데이트 하였습니다. 

 

def maxdrink(podojoo_list, T):
	if T == 1:
		return podojoo_list[0]
	elif T == 2:
		return podojoo_list[0] + podojoo_list[1]
	else:
		dp1 = 0
		dp2 = podojoo_list[0]
		dp3 = podojoo_list[0] + podojoo_list[1]

		for index in range(2, T):
			dp4 = max([dp3, dp2 + podojoo_list[index], dp1 + podojoo_list[index-1] + podojoo_list[index]])
			
			dp1 = dp2
			dp2 = dp3
			dp3 = dp4
		return dp3

podojoo_list = []
import sys

T = int(sys.stdin.readline())
podojoo_list = [int(sys.stdin.readline()) for _ in range(T)]

print(maxdrink(podojoo_list, T))