백준 2218, 상자 안의 구슬

개요

문제 링크
골드 3, DP

원소를 제거하며 얻을 수 있는 점수의 최댓값

---

접근

1. 접근 자체는 쉽지만 출력이 까다롭고 실수하기 좋다. 일단 N=1000이므로 O(N^2)에서 해결 가능.
2. dp[i][j]를 만든다. A상자에 i개, B상자에 j개가 있을 때 얻을 수 있는 최대 점수를 저장한다. dp[2][n] 등을 사용하면 안된다는 점에 주의할 것.
3. 그렇다면 비교할 값은? (i-1, j), (i, j-1), (i-1, j-1) 세 개가 된다. 각각 i, j개가 있으려면 i-1번째 a를 뽑거나, j-1번째 b를 뽑거나, 둘 다 뽑는 것이기 때문.
4. 이때 (i-1,j-1)번째는 a[i-1]과 b[j-1]을 뽑을 때 얻는 점수를 더해줘야 한다. 따라서 dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]+value[a[i-1]][b[j-1]])
   주의할 점은 value[i-1][j-1]이 아니라는 것이다.
5. 추가로 고려할 점은 만약 i=1이거나 j=1이면 둘 다 뽑을 수 없다는 것이다. i=1이면 뽑을 수 있는 것이 b뿐이므로 b를 뽑아야 한다.
6. 이때 출력을 해줘야 하므로 각각 어떤 action이 최적인지 dp에 같이 저장해준다.

---

Pseudo code

if (뺄 수 있는게 하나뿐)
    남은 것을 빼라
else if (a를 빼는게 이득)
    dp[i][j]의 이전위치 = i-1, j
    dp[i][j]의 action = 1
    dp[i][j]의 값 = dp[i-1][j]의 값
else if (b를 빼는게 이득)
    dp[i][j]의 이전위치 = i, j-1
    dp[i][j]의 action = 2
    dp[i][j]의 값 = dp[i][j-1]의 값
else if (둘 다 빼는게 이득)
    dp[i][j]의 이전위치 = i-1, j-1
    dp[i][j]의 action = 3
    추가점수 = value[a[i-1]][b[j-1]]
    dp[i][j]의 값 = dp[i-1][j-1]의 값 + 추가점수

---

Source code

#include <bits/stdc++.h>
using namespace std;

typedef struct {
    int value, act;
} node;

int main() {
    int n, a, b;
    cin >> n >> a >> b;
    int v[n+1][n+1];
    for (int i=0; i<=n; i++)
        v[i][0] = -2e9;
    for (int j=0; j<=n; j++)
        v[0][j] = -2e9;
    for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++)
            cin >> v[i][j];

    int va[a+1], vb[b+1];
    for (int i=1; i<=a; i++)
        cin >> va[i];
    for (int i=1; i<=b; i++)
        cin >> vb[i];
    va[0] = 0, vb[0] = 0;

    node dp[a+2][b+2];
    for (int i=0; i<=a+1; i++)
        for (int j=0; j<=b+1; j++) {
            dp[i][j].value = 0;
            dp[i][j].act = 0;
        }
    for (int i=1; i<=a+1; i++) {
        for (int j=1; j<=b+1; j++) {
            if (i==1 && j==1)
                continue;
            int ad = dp[i-1][j].value;
            int bd = dp[i][j-1].value;
            int dd = dp[i-1][j-1].value;
            dd += v[va[i-1]][vb[j-1]];

            if (i==1) {
                dp[i][j].value = bd;
                dp[i][j].act = 2;
            } else if (j==1) {
                dp[i][j].value = ad;
                dp[i][j].act = 1;
            } else if (dd <= ad && bd <= ad) {
                dp[i][j].act = 1;
                dp[i][j].value = ad;
            } else if (dd <= bd && ad <= bd) {
                dp[i][j].act = 2;
                dp[i][j].value = bd;
            } else {
                dp[i][j].act = 3;
                dp[i][j].value = dd;
            }
        }
    }
    int sa = a+1, sb = b+1;
    cout << dp[sa][sb].value << "\n";
    vector <int> q;
    while (1) {
        int act = dp[sa][sb].act;
        if (act)
            q.push_back(act);
        else
            break;

        if (act == 1)
            sa--;
        else if (act == 2)
            sb--;
        else if (act == 3)
            sa--, sb--;
    }
    for (int i = q.size()-1; i>=0; i--)
        cout << q[i] << " ";
}