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

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

2156번: 포도주 시식

백준 2156번 포도주 시식을 풀어봤습니다.

base condition과 점화식만 잘 설정해주면 됩니다.

 

아래는 전체 코드입니다.

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

int n;
int wine[10000];
int cost[10000];

int dp(int n) {
	if (n < 0)
		return 0;
	if (cost[n] != -1)
		return cost[n];
	if (n == 0)
		return cost[0] = wine[0];
	if (n == 1)
		return cost[1] = wine[0] + wine[1];

	cost[n] = max(max(dp(n - 3) + wine[n - 1] + wine[n], dp(n - 2) + wine[n]), dp(n - 1));
	return cost[n];
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> wine[i];
		cost[i] = -1;
	}
	
	dp(n - 1);

	int max = 0;
	for (int i = 0; i < n; i++)
		if (max < cost[i])
			max = cost[i];

	cout << max;

	return 0;
}