포도주 시식

문제 링크

발상

계단 오르기문제랑 비슷하지만 다른 문제다. 우선 계단 오르기 문제 처럼 마지막 포도주를 마실 것을 강제하지 않는다. 또한 연속하는 3개를 취할 수 없다는 점은 같지만 계단 오르기에서는 점프할 수 있는 거리를 2칸으로 강제한데 반해 포도주 문제는 주어진 점프 거리 제한이 없다. 어차피 배열에 양수만 주어지는데 2칸만 점프할거 아니냐 뭐가 다르냐 할 수 있지만 특정 경우 3칸을 점프하는게 이득인 입력이 있다.

100 100 0 0 100 100

계단 오르기 문제에서는 0을 반드시 한번은 밟고 100 한 칸을 놓칠 수 밖에 없지만, 포도주 문제에서는 3칸 점프를 통해 100만 고를 수 있다는 점이 다르다. 이 문제에서 취할 수 있는 옵션의 범위를 좁혀보자. 1칸 점프는 당연히 가능하고 2, 3칸 점프도 가능하다. 4칸 점프부터는 의미가 없다. 2칸씩 2번 점프한 것과 점프 거리는 같지만 중간의 1칸을 생략하는 꼴이기 때문에 절대 최적이 될 수 없다. 점프할 수 있는 옵션은 1, 2, 3 칸 총 3가지가 되고 조합 가지수가 많기 때문에 01타일문제 풀이처럼 옵션 조합의 범위를 체크하는 방법은 효율이 떨어진다. 따라서 이전에 연속으로 마신 횟수를 2번째 인자로 설정해 푸는 것이 가장 효율적인 풀이가 된다.

점화식

$$\{\begin{array}{l}{N}_{i,k}=\text{i위치 포도주까지 이전에 k상태로 연속해서 마셨을 때 최적값}\\ \text{1=추가 연속 가능:이전 포도주를 연속해 마시지 않은 경우}\\ \text{0=추가 연속 불가능:이전 포도주를 연속해 마신 경우}\\ A_i=\text{i위치 포도주 양}\end{array}$$ $$\begin{array}{rl}{N}_{i,0}& =N_{i-1,1}+A_i\\ N_{i,1}& =\max (\{\begin{array}{l}{N}_{i-2,0}\\ N_{i-2,1}\\ N_{i-3,0}\\ N_{i-3,1}\end{array})+A_i\end{array}$$

최대 2번까지 추가로 연속해서 마실 수 있으므로 $k$는 0 혹은 1이다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	int n; cin >> n;
	vector<int> arr(n + 1); vector<vector<int>> dp(n + 1, vector<int>(2));
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	int mx = 0;
	for (int i = 1; i <= n; i++) {
		int s1 = 0, s2 = 0, s3 = 0;
		s1 = dp[i - 1][1];
		if (i > 2) {
			s2 = max(dp[i - 2][0], dp[i - 2][1]);			
		}
		if (i > 3) {
			s3 = max(dp[i - 3][0], dp[i - 3][1]);			
		}
		dp[i][0] = s1 + arr[i];
		dp[i][1] = max(s2, s3) + arr[i];
		int cm = max(dp[i][0], dp[i][1]);
		mx = mx > cm ? mx : cm;
	}
	cout << mx;
	return 0;
}

실제로 문제를 풀기 전에 풀이를 구상하는 과정은 알고리즘 종류를 떠나서 매우 중요하다. 아니 사실 코딩이 아니라 어떤 분야에서도 중요하다. 이미 알고있는 데이터에서 필요한 정보를 선별하고 문제가 어떤 문제인지 파악하고 풀이를 머릿 속으로 떠올리는 과정을 반복적으로 거쳐야 좋은 실력을 얻을 수 있다.