백준_2156_포도주 시식

다이나믹 프로그래밍(dp) 문제였다.

d[i]가 i번째잔까지 왔을때 포도주를 최대로 마신 양 이라고 할 때, d[1]은 당연히 첫번째 잔을 마시는 것이고, d[2]는 첫번째 잔과 두번째 잔을 모두 마시는 것이다. 이후에는, 3가지 경우가 존재한다.

 

① 현재 i번째 잔을 안마시는경우

② 현재 i번째 잔을 마시는데, 그 전 i-1번째 잔은 안마신 경우

③ 현재 i번째 잔을 마시는데, 그 전 i-1번째 잔도 마신 경우 -> 이 경우, i-2번째 잔은 안마셨어야 함.

 

이 3가지 경우 중 최댓값이 d[i]다.

#include <iostream>
#include <algorithm>
#define MAX 10001

using namespace std;

int n, d[MAX], wine[MAX];

void dp() {
	d[1] = wine[1];
	d[2] = wine[1] + wine[2];
	for (int i = 3; i <= n; i++) {
		d[i] = max(d[i - 1], max(d[i - 2] + wine[i], d[i - 3] + wine[i - 1] + wine[i]));
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> wine[i];
	}
	dp();
	cout << d[n] << '\n';
	return 0;
}