백준 2156: 포도주 시식

문제 요약

일렬로 놓인 포도주의 양이 주어지면, 다음의 조건을 만족하면서 마시는 포도주의 최댓값을 출력한다.
1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

문제 분류

• 다이나믹 프로그래밍

문제 풀이

우선, i번째의 포도주의 양은 v[i], i번째까지의 포도주 중에서 최대로 마셨을때의 양 dp[i]로 하자.

dp[i]는 v[i]를 마신 경우와 그렇지 않은 경우로 나누어서 각 경우의 최댓값을 대입하면 된다.

v[i]를 마신다고 하면, dp[i - 2] + v[i]와 v[i - 1] + dp[i - 3] + v[i]의 최댓값을 dp[i]에 넣어줘야 한다. 3잔 이상 연속된 포도주를 마시면 안 되기 때문이다.

v[i]를 마시지않는 경우 단순히 dp[i - 1]을 넣어주면 된다. 즉, 이 모든 3가지 중의 최댓값을 넣어주면 된다.

즉, 포도잔을 연속된 3잔을 마시지 않기 위해 이런 번거로운 일을 하는 것이다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int dp[10001];

int main()
{
	int n, in;
	vector<int> v;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &in);
		v.push_back(in);
	}
	dp[0] = v[0];
	if (n > 1) {
		dp[1] = v[0] + v[1];
		if (n > 2) {
			dp[2] = max(dp[1], v[1] + v[2]);
			dp[2] = max(dp[2], v[0] + v[2]);
		}
	}
	for (int i = 3; i < n; i++) {
		dp[i] = max(v[i] + dp[i - 2], v[i] + v[i - 1] + dp[i - 3]);
		dp[i] = max(dp[i], dp[i - 1]);
	}
	cout << dp[n - 1];
}