알고리즘/PS

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

BigmacGood 2022. 4. 3. 15:47

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

 

2156번: 포도주 시식

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규

www.acmicpc.net

백준 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;
}