본문 바로가기

Problem Solving/Algorithm Training

[Baekjoon] 2156 - 포도주 시식 (C++)

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

 

2156번: 포도주 시식

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고

www.acmicpc.net

꽤나 고민했던 문제였습니다. DP(dynamic programming)로 풀어야 한다는 것은 알겠는데, 어떻게 접근을 해야 할지 잘 모르겠더군요. 그러다가 어느 수학 문제에서 점화식을 세우는 것을 보고 이 문제도 혹시나 해서 같은 방법으로 접근해 보았습니다. 다행히 잘 풀렸네요!

 

이번 문제는 점화식으로 접근해 보았습니다. 먼저 DP 배열을 하나 만들겠습니다. 이 배열은 1번부터 i번까지의 잔 중에서 문제의 조건에 맞게끔 잔을 골라 최대로 많이 마실 수 있는 양이 기록되어 있습니다. 예를 들어 DP[3]의 경우 1번부터 3번까지 3개의 잔에서 골라 마셨다는 뜻이 됩니다. 이제 i번째 잔을 고른 경우와 고르지 않은 경우를 고려해 식을 세워보면 다음과 같습니다.

 

1. i번째 잔고른 경우

이는 다시 2가지 상황으로 나눌 수 있습니다.

 

1.1. i번째 잔i - 1번째 잔고른 경우

이 경우 i - 2번째 잔은 연속으로 놓여있기 때문에 선택할 수 없습니다. i - 3번째 잔부터 골라야겠죠? 그런데 우리는 이미 1번부터 i - 3번째 잔까지 골랐을 때의 최댓값을 알고 있습니다. 바로 DP[i - 3] 값이죠. 따라서 이 경우에 마실 수 있는 최대의 양은 아래와 같습니다. (\( a_i \) 값은 i번째 잔의 양을 의미합니다.)

\[ a_i + a_{i-1} + DP[i-3] \]

 

1.2. i번째 잔i - 2번째 잔고른 경우

이 경우 1번부터 i - 2번째 잔까지 고른 최댓값에 i번째 잔의 양만 더해주면 됩니다. 따라서 이 경우에 마실 수 있는 최대의 양은 아래와 같습니다.

\[ a_i + DP[i-2] \]

 

2. i번째 잔고르지 않은 경우

이 경우는 그냥 1번부터 i - 1번째 잔까지 고른 최댓값이 됩니다. 따라서 이 경우에 마실 수 있는 최대의 양은 아래와 같습니다.

\[ DP[i-1] \]

 

1번부터 i번째 잔까지 골라서 마실 수 있는 양의 최댓값을 DP[i]로 정의했었죠? 따라서 위에서 구한 식을 이용해 DP[i]에 대한 점화식을 아래와 같이 세울 수 있습니다.

\[ DP[i] = \textrm{max} ( \color{red} a_{i}+a_{i-1}+DP[i-3] \color{black} , \  \color{green} a_{i}+DP[i-2] \color{black} , \  \color{blue} DP[i-1] \color{black} ) \]

구분하기 쉽게 색을 다르게 줬습니다. DP[i] 값은 저 3가지 경우에서 제일 큰 값을 골라주시면 됩니다. 이제 위 점화식을 그대로 반복문 등을 이용해 구현하기만 하면 되겠죠? 초깃값의 경우엔 점화식을 보면 DP[i - 3] 값까지 쓰이고 있으므로 처음 DP 배열 3개 부분은 직접 설정한 뒤 반복해서 돌려주셔야 합니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

	int n;
	cin >> n;

	vector<int> arr(n);
	vector<int> dp(n);

	// 포도주 데이터 입력
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	// 초깃값 설정 (동적 계획법)
	// 잔을 하나씩 늘려가면서 최대로 마실 수 있는 양을 계산하는 방식
	// 1잔, 2잔, 3잔의 경우는 직접 계산해서 미리 기록
	if (n >= 1) dp[0] = arr[0];
	if (n >= 2) dp[1] = arr[0] + arr[1];
	if (n >= 3) dp[2] = max(max(arr[0] + arr[1], arr[1] + arr[2]), arr[0] + arr[2]);

	// 점화식을 만들어서 나머지 부분 계산
	for (int i = 3; i < n; i++) {
		dp[i] = max(max(dp[i - 1], dp[i - 2] + arr[i]), dp[i - 3] + arr[i] + arr[i - 1]);
	}

	cout << dp[n - 1] << "\n";
	return 0;
}