문제 풀이

딱 봐도 DP냄새를 풍기는 문제
int d[i][j]의 이차원 배열로 i번째 포도주 까지 j번 연속해서 마셨을 때 포도주의 최대 양이라고 했을 때

d[i][0]은 i번째 포도주를 안마셨을경우고

• 이전에 2번 연속으로 마셨을때 최대량
• 이전에 1번 마셨을 때 최대량
• 이전에 안마셨을 때 최대량
  중에 최대가 될 것이고,

d[i][1]은 i번째 포도주를 마셨지만 연속 해서 마시지 않았을 경우이므로

• 이전 포도주를 안마셨을 때 최대양 + 현재 포도주의 양
  이 될 것이며,

d[i][2]는

• 이전 포도주를 마셨고 이번 포도주도 마셨을 때이다.

그럼 출력은 이 모든것들 중에 최대이면 된다.

문제 링크

boj/2156

소스코드

PS/2156.cpp

#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>
using namespace std;

int d[10001][3];
int arr[10001];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n;
	cin >> n;
	
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}
	
	int ans = 0;
	d[0][1] = arr[0];
	d[1][0] = arr[0];
	d[1][1] = arr[1];
	d[1][2] = arr[0] + arr[1];
	ans = d[1][2];
	
	for (int i = 2; i < n; i++)
	{
		d[i][0] = max(d[i][0], d[i - 1][2]);
		d[i][0] = max(d[i][0],max(d[i - 1][0], d[i - 1][1]));
		
		d[i][1] = max(d[i][1],d[i-1][0]+arr[i]);

		d[i][2] = d[i - 1][1] + arr[i];
		ans = max(ans, d[i][0]);
		ans = max(ans, d[i][1]);
		ans = max(ans, d[i][2]);
	}

	cout << ans;
}