[BOJ] 2156 포도주 시식 - 동적 계획법

수열에서 N 위치까지의 원소의 합의 최대값을 구한다고 했다.

대신, 연속해서 3번이상 원소를 선택할 수 없다.

 

그렇다면, 합의 최대값을 MaxSumUntil[N] 이라고 한다면,

 

경우의 수를 다음과 같이 나눌 수 있다.

1. N번째 숫자를 고르지 않는 경우.

이 경우 MaxSumUntil[N] 은 MaxSumUntil[N - 1] 을 그대로 따라가게 된다.

 

2. N번째 숫자를 고르고, N - 1번째 숫자도 고르는 경우.

이 경우 N - 2번째 숫자는 고를 수 없다.

따라서 MaxSumUntil[N-3] + Element[N-1] + Element[N] 이 된다.

 

3. N번째 숫자를 고르고, N - 1번째 숫자를 고르지 않는 경우.

이 경우 MaxSumUntil[N-2] + Element[N] 이 된다.

 

숫자를 고르지 않는 경우도 계산해서 최대값을 갱신한다.

따라서 MaxSumUntil[N]은 해당 Element[N]를 고른 경우의 값을 담고 있을수도,

고르지 않은 경우의 값을 담고 있을수도 있다.

점화식으로 만들어진 배열에 담긴 값은 1번의 조건이 적용되어 있다는 것을 기억한다.

 

그림을 보면 N = 6일때

첫번째 경우를 고르게 되면,  200이전의 100이란 값을 놓친다.

N = 4를 고를 수 밖에 없는 경우 이기 때문이다.두번째 경우를 고르게 되면, 답이 된다. MaxSumUntil 이 자신을 고르지 않는 경우인  O O X 이기 때문이다.  

 

 

#include <iostream>
#include <algorithm>
 
int MaxSumUntil[10001] = { 0 , };
int Cost[10001] = { 0, };
 
int main()
{
	std::cin.tie(0);
	std::cout.tie(0);
	std::cin.sync_with_stdio(false);
	std::cout.sync_with_stdio(false);
 
	int N;
	std::cin >> N;
 
	for (int i = 1; i <= N; ++i)
		std::cin >> Cost[i];
 
	MaxSumUntil[1] = Cost[1];
	MaxSumUntil[2] = Cost[1] + Cost[2];
	MaxSumUntil[3] = std::max(Cost[1] + Cost[3], Cost[2] + Cost[3]);
	MaxSumUntil[3] = std::max(MaxSumUntil[3], Cost[1] + Cost[2]);
 
 
	if (N <= 3)
	{
		std::cout << MaxSumUntil[N] << std::endl;
		return 0;
	}
		
	for (int i = 4; i <= N; ++i)
	{
		MaxSumUntil[i] = std::max(MaxSumUntil[i - 1], MaxSumUntil[i - 2] + Cost[i]);
		MaxSumUntil[i] = std::max(MaxSumUntil[i], Cost[i] +  MaxSumUntil[i - 3] + Cost[i - 1]);
	}
 
	std::cout << MaxSumUntil[N] << std::endl;
	return 0;
}