포도주 시식

---

풀이

여러가지를 선택하는 것들중 최적의 방법으로 선택을 하는 문제는 대부분 DP로 풀리는거같다.
이 문제도 보자마자 DP가 떠올랐다.

dp[N] = S // N잔의 포도잔중 가장 많이 마시는 량

이 문제의 조건은 연속해서 3잔을 마시지 못하는경우이기때문에
N번째잔을 마시는경우와 마시지 않는경우로 나누었다.

1. N번째잔을 마시지 않는경우 dp[n]=dp[n-1]

N번째 잔을 마시는경우에서

N-1번째 잔을 마시는경우 N-2번째 잔을 마실수 없다.
2. dp[n]=wine[n]+wine[n-1]+dp[n-3]
N-1번째 잔을 마시지 않는경우
3. dp[n]=wine[n]+dp[n-2]

1,2,3 번중 최대값을 dp[n]으로 정하면 된다.
즉. dp[i] = max(max(dp[i - 3] + wine[i - 1] + wine[i], dp[i - 2] + wine[i]), dp[i - 1])

---

실제코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <math.h>
using namespace std;
#define endl "\n"

#define MAX 10000+1

int N;
int dp[MAX];
int wine[MAX];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//ifstream cin; cin.open("input.txt");

	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		cin >> wine[i];
	}
	dp[0] = 0;
	dp[1] = wine[1];
	dp[2] = wine[1] + wine[2];
	
	
	for (int i = 3; i <= N; i++)
	{
		dp[i] = max(max(dp[i - 3] + wine[i - 1] + wine[i], dp[i - 2] + wine[i]), dp[i - 1]);
	}

	cout << dp[N];
}