(백준/C++) 2156_포도주 시식

2156번: 포도주 시식 문제는 동적 계획법(Dynamic Programming)으로 풀어내는 문제이지만, 동적 계획법으로 풀어낼 때, 점화식을 생각하는데 어려울 수 있습니다.

규칙은 다음과 같습니다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

이에따라 연속으로 3잔을 마실 수 없고, 최대 마실 수 있는 양을 저장해야 하는데, 어디에 저장해서 어떤 값을 써야할지 감을 잡지 못할 수 있습니다.

우선, 동적 계획법(Dynamic Programming, DP)이란, 큰 문제를 작은 문제들로 나누어 풀어나가고 작은 문제의 해를 저장해 다시 계산하지 않고 사용하는 방식입니다.

동적 계획법 문제는 최적 부분 구조와 중복된 부분 문제의 두 가지 속성을 가집니다. 이 문제도 최적 부분 구조와 중복된 부분 문제에 대해 먼저 생각해보겠습니다.

1. 최적 부분 구조: 최적 부분 구조란 큰 문제를 작은 문제로 나누고 작은 문제의 최적 해가 큰 문제의 최적 해가 될 수 있는 구조입니다.
   이 문제는 연속 세 잔을 마실 수 없는 제약 조건 하에서 현재 잔을 마시거나 건너뛰거나 해야 하는데, 이전 잔들의 해결 방법을 기반으로 현재 잔에서의 최적의 해결 방법을 찾을 수 있으리라고 생각합니다.
   이 부분을 최적 부분 구조라고 생각합니다.
2. 중복된 부분 문제: 문제를 풀다 보면 특정 번째의 포도주 잔에서의 최대로 마실 수 있는 양을 계속 참조하게 됩니다.
   이러한 중복된 부분 문제를 메모이제이션(Memoization)을 통해 한 번만 계산하고 결과를 저장하고 재활용할 수 있습니다.

---

접근법

1.Top-down식 생각하기

먼저, 현재 잔을 마시는 경우와 마시지 않는 경우로 나누어 생각하면, 연속된 세 잔을 마시지 않도록 제어할 수 있습니다.

1. 현재 잔을 마시지 않는 경우: 이전 잔에서 계산한 양에서 최대 양을 그대로 가져옵니다.
2. 현재 잔을 마시는데, 이전 잔을 마시지 않은 경우: 이전 잔에서 이미 1.에서 최대 양을 계산했기 때문에, 이전에 마시지 않은 양에서 현재 잔의 양을 계산합니다.
3. 연속해서 두 잔을 마시는 경우: 연속해서 두 잔을 마시려면 이전 잔을 마셨어야 하는데, 이전 이전 잔은 마시지 않은 경우여야합니다. 따라서 이전 잔에서 2.에서 계산한 양을 이용해야 합니다.

2.점화식 찾기

위에서 연속 세 잔을 마시지 않게 설계했으므로, 위 세가지 경우에 대한 점화식을 찾고 계산해야 합니다.

1. selected[i][0]: i번째 잔을 마시지 않은 경우, i-1번째 잔까지의 최대값과 같음
2. selected[i][1]: i번째 잔을 마시고, 이전 잔은 마시지 않은 경우, selected[i-1][0]이 이전 잔에서 마시지 않은 경우이므로 이를 이용
3. selected[i][2]: i번째 잔과 이전 잔을 모두 마신 경우, selected[i-1][1]을 사용해야 연속 세 잔을 마시지 않고 이전 잔을 마신 경우가 될 수 있음

---

풀이

이번 문제는 제 기준에서 점화식을 찾기 매우 어려운 문제에 속했습니다.

만약, 위의 내용을 보고 점화식을 찾으셨다면 다음과 같은 덤화식을 도출할 수 있었을 겁니다.

• selected[i][0] = max(selected[i - 1][0], selected[i - 1][1], selected[i - 1][2])
• selected[i][1] = selected[i - 1][0] + wine[i]
• selected[i][2] = selected[i - 1][1] + wine[i]

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> wine;
vector<vector<int>> selected;
void taste(int N)
{
	// 첫 번째 잔에 대한 선택
	selected[1][1] = wine[1];

	for(int i = 2; i <= N; i++)
	{
		// 이번 잔을 마시지 않는 경우
		selected[i][0] = max({selected[i - 1][0], selected[i - 1][1], selected[i - 1][2]});
		// 연속 한 잔만 마시는 경우 (이번 잔부터 다시 시작하는 경우)
		selected[i][1] = selected[i - 1][0] + wine[i];
		// 연속 두 잔째 마시는 경우 (이전 잔을 마셨음)
		selected[i][2] = selected[i - 1][1] + wine[i];
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N;
	cin >> N;

	wine.resize(N + 1);
	selected.resize(N + 1, vector<int>(3));
	for(int i = 1; i <= N; i++)
		cin >> wine[i];

	taste(N);

	cout << max({selected[N][0], selected[N][1], selected[N][2]});
}

이 코드에서 std::max 함수를 사용할 때 중괄호 {}를 이용하는 것은 C++11 이상의 버전에서 사용 가능한 기능으로, initializer_list를 사용한 것입니다.

중괄호 {} 안에 있는 여러 개의 값을 initializer_list로 감싸면, std::max 함수는 이 리스트의 모든 요소 중에서 가장 큰 값을 찾을 수 있습니다.