[백준 C++] 2156번: 포도주 시식

https://www.acmicpc.net/problem/2156

 

dp문제이고 포도주의 양을 점수로 생각했을때 가장 많은 점수를 얻는 뭐 그런식의 문제라 이해했다.

 

n= 10001 까지이고, dp[n]을 n까지의 최대 마실수 있는 포도주의 양이라 하였을때,

dp[1]은 당연히 a[1]이고

dp[2]은 당연히 a[1] + a[2] 이라 했을 때 

dp[3]는 a[1] + a[2] + a[3]를 할 수 없으므로 a[1] + a[2], a[1] + a[3], a[2] + a[3]의 최대값을 비교해야한다.

 

따라서

N-4

N-3

N-2

N-1

N

 

이 표 처럼 dp와 a 배열이 구성된다 하였을때

 

dp[N]값은

 

dp[N-3] + a[N-1] + a[N]

 

vs

 

dp[N-2] + a[N]

 

vs

 

dp[N-1] 이중 가장 큰값으로 구성된다.

 

즉, 어느 번째 포도주를 안마실 꺼냐 라는거다.

 

#include <iostream>
#include <algorithm>
#define MAX 10001
using namespace std;
int dp[MAX] = { 0, };
int a[MAX] = { 0, };
int main(int argc, char* argv[])
{
	int n;
	cin >> n;
 
	for (int i = 0;i < n;i++) {
		cin >> a[i];
	}
 
	dp[0] = a[0];
	dp[1] = a[0] + a[1];
	dp[2] = max(max((a[0] + a[1]), (a[1] + a[2])), (a[0] + a[2]));
 
 
	for (int i = 3;i < n;i++) {
		dp[i] = max(max((dp[i - 3] + a[i - 1] + a[i]), (dp[i-2] + a[i])), dp[i-1]);
 
	}	
 
	cout << dp[n-1];
 
	return 0;
}

 

어렵다..