백준 포도주 시식 코드 및 해설 (파이썬)

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

2156번: 포도주 시식

 

다이나믹 프로그래밍 문제다. 연속적으로 3잔의 포도주를 먹을 수 없다는 제한이 있다. 

i번째 포도주에 해당하는 dp값은 i번째 포도주를 마시는 경우와 마시지 않는 경우로 나눌 수 있는데

(1) i번째 포도주를 마시는 경우

(1.1) i-1번째와 i번째 포도주를 마시는 경우: i-2번째는 먹지 못하니까 dp[i-3] + wine[i-1] + wine[i]

(1.2) i-1번째 포도주는 마시지 않고 i번째 포도주만 마시는 경우: i-2번째도 마실 수 있으니 dp[i-2] + wine[i]

(2) i번째 포도주를 마시지 않는 경우

i-1번째까지 최댓값을 구하면 되니까 dp[i-1] 

이 모든 경우 중 최댓값을 취하면 된다 

 

import sys

n = int(sys.stdin.readline())
wine = []
for _ in range(n):
    wine.append(int(sys.stdin.readline()))

if n < 3:
    print(sum(wine))

else:
	dp = [0] * n

	dp[0] = wine[0]
	dp[1] = dp[0] + wine[1]
	dp[2] = max(wine[0] + wine[2], wine[1] + wine[2], dp[1])

	if n > 3:
		for i in range(3, n):
			# i번째 포도주를 마신 경우
				# i-1, i번째 포도주를 마신 경우: dp[i - 3] + wine[i - 1] + wine[i]
				# i-1번째 포도주는 마시지 않고 i번째 포도주만 마신 경우: dp[i - 2] + wine[i]
			# i번째 포도주를 마시지 않은 경우: dp[i-1]
			dp[i] = max(dp[i - 3] + wine[i - 1] + wine[i], dp[i - 2] + wine[i], dp[i - 1])

	print(dp[-1])