[C++] 백준 2156 [포도주 시식]

문제설명

수열의 원소 N개 중 합이 최대가 되도록 원소를 선택하되, 연속된 3개의 수는 선택하지 못한다.
선택한 원소들의 합을 출력한다.

풀이방법

Top-down 풀이방식이다.
Cache array는 이중 배열로 구현하였다.
DP(a, b)의 정의 : b번째 원소까지의 연속된 3개의 수를 선택하지 않은 원소들의 합의 최대값(단, b번째 원소 이후로 b와 연속된 원소의 개수는 a개)
grape[b] : b번째 원소

점화식

\(DP(0, b) = max(DP(0, b-1), DP(1, b-1) + grape[b]\)
\(DP(1, b) = max(DP(0, b-1), DP(2, b-1) + grape[b]\)
\(DP(2, b) = DP(0, b-1)\)

문제의 답은 DP(0, N)이다. N번째 원소가 마지막이기 때문에, a가 0인 경우만 가능하다.
DP(0, b)은 원소 n을 선택하거나, 선택하지 않을 수 있다.
만약 선택한다면, b-1번째 원소는 b과 연속하기 때문에 DP(1, b-1)으로, a가 1이 된다. 그러므로 grape[b] + DP(1, b-1)이다.
만약 선택하지 않는다면 연속하지 않기 때문에 DP(0, b-1)이 된다.
우리는 최대값을 찾아야 하므로, max(DP(0, b-1), DP(1, b-1) + grape[b])이 된다.
DP(1, b)의 경우, b+1번째 값을 선택한 상태이므로, 현재 원소를 선택하게 되면 grape[b] + DP(2, b-1)이 되고, 선택하지 않으면 DP(0, b-1)이 된다.
그러므로 max(DP(0, b-1), DP(2, b-1) + grape[b])가 된다.
DP(2, b)의 경우, b+1번째와 b+2번째 값을 선택한 상태이므로, 현재 원소를 선택할 수 없어서 DP(0, b-1)이 된다.
이 세개의 점화식을 활용하여 아래와 같이 코드를 작성할 수 있다.

소스코드

#include<iostream>
#include<vector>
#include<cstring>

using namespace std;

vector<int> grape;
int cache[3][10001];

int DP(int a, int b){
    if(a == 2 && b == 1) return 0;
    if(b == 1) return grape[0];

    int& ret = cache[a][b];
    if(ret != -1) return ret;

    if(a == 0) ret = max(DP(0, b-1) ,DP(1, b-1) + grape[b-1]);
    if(a == 1) ret = max(DP(0, b-1) ,DP(2, b-1) + grape[b-1]);
    if(a == 2) ret = DP(0, b-1);

    return ret;
}

int main(){
    int N;
    cin >> N;
    memset(cache, -1, sizeof(cache));
    for(int i=0; i<N; i++){
        int n;
        cin >> n;
        grape.push_back(n);
    }
    cout << DP(0, N);
}