[백준 / BOJ] 2156: 포도주 시식

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

2156번: 포도주 시식

 

 

---

 

코드

---

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n, ar[10001], dp[10001] = {};

	cin >> n;

	for (int i = 1; i <= n; i++)
		cin >> ar[i];

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

	cout << dp[n];
	return 0;
}

 

 

 

---

 

 

백준 2579번 계단오르기 문제와 유사하다.

다른 점이 있다면, 계단 오르기 문제에서는 반드시 마지막 계단을 밟아야 했지만, 포도주 시식 문제에서는 마지막 잔을 반드시 선택할 필요는 없다는 것이다.

이 한가지의 차이 때문에, 세 개의 잔을 연속하여 선택할 수 없다는 규칙을 만족하며 문제를 풀기 위한 경우의 수가 다음과 같이 세 가지로 나뉘게 된다.

1. n번 잔을 선택하고, n-2번 잔을 고려한다.
2. n번 잔과 n-1번 잔을 선택하고, n-3번 잔을 고려한다.
3. n번 잔을 선택하지 않고, n-1번 잔을 고려한다.

따라서 첫번째 잔부터 i번째 잔까지 최대로 마실 수 있는 포도주의 양을 dp[i], i번 잔의 포도주 양을 ar[i]라고 할 때, 점화식은 dp[i] = max(max(dp[n-2] + ar[i], dp[i-3] + ar[i-1] + ar[i]), dp[i-1]) 와 같이 나타낼 수 있다.