포도주 시식 (백준 - 2156번)

동적 계획법을 사용하여 해결하는 문제이다.

 

연속으로 놓여있는 3잔을 마실 수 없기 때문에 세가지 경우가 도출된다.

 

N개의 와인잔이 있다고 가정했을때, 처음부터 N번째 까지 차례대로 최대로 마신 양을 기록한다고 하자. N번째 와인잔에서는...

 

1. 해당 번째 와인을 마시지 않는 경우 : 그러면 이전 와인에서 최대로 마신 양이 된다. 

 

2. 해당 번째 와인을 마시고 이전이전 와인을 마시는 경우 : 그러면 이전이전 와인에서 최대로 마신 양과 N번째 와인의 양의 합이다.

 

3. 해당 와인을 마시고 이전 와인을 마시고, 3잔 이상인 경우, 연속으로 놓여있는 3잔을 마실 수 없기 때문에 이전이전이전 와인을 마신다 : 이전이전이전 와인에서 최대로 마신 양과 이전 와인와 양 그리고 N번째 와인의 양를 모두 더한다.

 

 

이제 위 경우를 만족하는 점화식을 만들어보자.

 

N개의 와인잔이 있다고 했을때, 최대로 마신 양을 기록할 DP테이블 배열 DP[N+1] (인덱스 접근은 0부터 시작이므로 크기를 하나 더 할당한다)과 와인잔에 들어있는 와인양을 기록할 배열 wine[N+1]을 선언한다.

 

우선 첫번째와 두번째의 경우는 다음으로 고정이다.

 

첫번째 와인에서의 DP[1]은 와인이 하나 밖에 없으므로 무조건 마시는게 최대이다. 그러므로 DP[1] = wine[1]이다.  

그리고 두번째 와인에서의 DP[2]는 두개의 와인이 있고 두개 모두 마시는 것은 조건을 만족하므로 모두 마시는 것이 최대값일 것이다. 그러므로 DP[2] = wine[1] + wine[2]이다. 

 

이제 3번째부터 n번째 까지의 와인 DP[3] ~ DP[n]까지 경우를 살펴보자. 위 세가지 경우를 점화식으로 표현했을때  첫 번째 경우는 DP[X] = DP[X-1], 두 번째 경우는 DP[X] = DP[X-2] + wine[X], 그리고 세번째 경우는 DP[X] = DP[X-3] + wine[X-1] + wine[X]가 된다.

 

이제 DP[X-1], DP[X-2] + wine[X], DP[X-3] + wine[X-1] + wine[X] 중 가장 큰 값을 DP[X]에 넣어주면 된다. 그리고 DP[N]에서 우리가 찾는 값이 나온다. 

 

코드는 다음과 같다.

#include <iostream>
using namespace std;

int max(const int& a, const int& b, const int& c)
{
	return a > b ? (a > c ? a : c) : (b > c ? b : c);
}

int main()
{
	int input = 0;
	cin >> input;

	int* wines = new int[input + 1];
	int* dp = new int[input + 1];
	for (int i = 1; i <= input; ++i)
	{
		cin >> wines[i];
		dp[i] = 0;
	}

	dp[0] = 0;
	dp[1] = wines[1];
	if (input > 1)
	{
		dp[2] = wines[1] + wines[2];
	}
	if (input > 2)
	{
		for (int i = 3; i <= input; ++i)
		{
			dp[i] = max(dp[i - 1], dp[i - 2] + wines[i], dp[i - 3] + wines[i - 1] + wines[i]);
		}
	}

	cout << dp[input] << endl;
	delete[] wines;
	delete[] dp;
}