BOJ [포도주 시식]

문제

문제 보기

요약하면 양이 다른 포도주잔이 쭉 놓여 있다. 세 잔 연속해서 마시는 것이 불가능 할 때 마실 수 있는 최대한의 포도주양을 구하라는 문제이다.

풀이

아이디어만 떠올리면 쉽게 풀리는 문제였다. 예전에 dp를 처음 배울 때 '타일 설치'문제를 기억하라.

문제는 좀 다르지만 경우를 나누는 법은 같다. 세로 타일을 놓으면 그 칸과 옆칸은 이어질 수 없다. 하지만 2*2나 가로 타일을 놓으면 옆칸과 이어질 수 있다. 즉 dp를 사용해서 푸는데 dp[i-1]에 세로타일을 놓는 경우와 dp[i-2]에 가로나 2*2타일을 놓는 경우 두 가지가 있다.

이번 문제도 똑같다. 단지 경우가 한 가지 추가될 뿐이다. 포도주를 먹는 경우를 2*1, 1*1 두가지 종류의 타일로 보자. 타일은 이웃해서 설치할 수 없다. 이러면 포도주를 먹는 모든 경우를 구할 수 있다.

그러면 dp[i]는 어떻게 될 까? 우선 dp[i]의 의미는 '0번 부터 i번 째 칸까지 왔을 때 가장 많이 먹은 포도주양'이다. 그 계산법은 다음과 같다.

max(dp[i-3]+wine[i-1]+wine[i],dp[i-2]+wine[i],dp[i-1])

i-1과 i를 먹는 경우, i-1을 먹지않고 i만 먹는 경우, i를 먹지 않는 경우 세가지 이다. dp[i]에서는 i만 신경쓰면 되므로 i를 먹지 않을 때 i-1은 신경쓸 필요가 없다. dp[i-1]에서 알아서 해준다.

코드

n = int(input())

wine=[]
for _ in range(n):
	wine.append(int(input()))
if n == 1:
	dp = [wine[0]]
else:
	dp = [wine[0],wine[0]+wine[1]]

	if n >2:
		dp.append(max(dp[1],wine[1]+wine[2], wine[0]+wine[2]))

for i in range(3,n):
	dp.append(max(dp[i-3]+wine[i-1]+wine[i],dp[i-2]+wine[i],dp[i-1]))

print(max(dp))