백준 2156 C++ - 포도주 시식

Intro

문제해결 및 소스코드

#include <iostream>
#include <algorithm>
using namespace std;

/*									<문제해결>
		규칙1. 연속으로 놓인 3잔을 모두 마실 수 없다.

		dp로 문제를 해결하기 위해 주어진 포도주 + 맨 처음에 있는 가상의 포도주 1잔이 있다고 가정했다.
		예제를 살펴보면, 포도잔이 6개 있다. 여기에 가상의 포도주를 추가했다.
		0, 6, 10, 13, 9, 8, 1

		먼저 초기값을 설정했다.
		dp[0] = 0, dp[1] = 6, dp[2] = 16	

		dp[3]을 구하려고 하니, 다음 세가지 방법으로 구할 수 있었다.
		1. 0번째잔 + 2번째잔 + 3번째잔
		2. 1번째잔 + 3번째잔
		3. 2번째잔 까지의 최대합

		따라서 n번째잔 까지의 합 dp[n]은
		1. n-3번째잔 까지의 최대합 + n-1번째잔 + n번째 잔
		2. n-2번째잔 까지의 최대합 + n번째 잔
		3. n-1번째잔 까지의 최대합
		중 가장 큰 값이 된다.
*/

int arr[10001];
int dp[10001];

int main(void)
{
	int n;
	cin >> n;

	for (int i = 1;i <= n;i++)
	{
		cin >> arr[i];
	}

	dp[1] = arr[1];
	dp[2] = arr[1] + arr[2];

	for (int i = 3;i <= n;i++)
	{
		dp[i] = max(dp[i - 1], max(dp[i - 2] + arr[i], dp[i - 3] + arr[i - 1] + arr[i]));
	}

	cout << dp[n];
	return 0;
}