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;
}