포도주 시식

알고리즘 구분 : 다이나믹 프로그래밍

문제 풀이 : 이 문제에서 명확히 정의되어 있는 2가지 규칙이 있다. 첫 번째는 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다는 것이고, 두 번재는 연속으로 놓여 있는 3잔을 모두 마실 수는 없다라는 것이다.
첫 번째 규칙은 마신 후에도 위치가 유지되므로 index에서는 변화가 없다는 것이다.
두 번째 규칙으로 인해 해당 문제를 DP로 풀어야 할 것이라는 방향성을 얻을 수 있었다. 그렇다면 DP에 필요한 점화식은 무엇이 될 것인지 생각해 보았다. 연속으로 놓여 있는 3잔을 모두 마실 수 없다는 것의 의미는 최대 2잔을 연속으로 마실 수 있다는 의미가 되며, 이를 3잔이 놓여 있는 상황으로 가정하였을 때, O X O, O O X, X O O, O X X, X O O의 경우의 수가 존재한다. 이를 3번째에 위치한 잔의 관점에서 기준으로 보았을 때, 두 번째 잔을 마시지 않거나 또는 첫 번째 잔을 마시지 않거나로 구분할 수 있게 된다. dp[i] = max(dp[i - 3] + arr[i] + arr[i - 1], dp[i - 2] + arr[i])의 점화식으로 표현이 가능한 것이다. 여기서 max함수 안에 dp[i - 3]이 들어가는 이유는 결국 첫 번째 잔을 마시지 않으면, 그 이전 잔까지의 최대 합을 끌고와서 계산해야 하기 때문이다.
여기서 조심해야할 점은 처음에 문제를 풀 때, 두 잔을 연속적으로 마시지 않는 경우의 수는 존재하지 않을 것으로 보았다. 너무 당연시하게 생각했었지만, 문제를 푸는 과정에서 해당 과정도 충분히 존재할 수 있을 것이라는 판단이 되어, 그 부분을 해결하기 위하여 dp[i] = max(dp[i - 1], dp[i])를 사용하여 3번째 위치의 잔도 마시지 않고, 2번째 위치의 잔도 마시지 않는 경우의 수에 대한 비교할 수 있게 하였다.

소스 코드 :

#include <bits/stdc++.h>

using namespace std;

int n;
int arr[10001];
int dp[10001];


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	
	dp[1] = arr[1];
	dp[2] = dp[1] + arr[2];
	for(int i = 3; i <= n; i++) {
		dp[i] = max(dp[i-3] + arr[i] + arr[i-1], dp[i-2] + arr[i]); 
		dp[i] = max(dp[i-1], dp[i]);
	}
	
	cout << dp[n] << endl;
	
	return 0;
}

• 문제 출처 : https://www.acmicpc.net/problem/2156
• 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.