BOJ 10468 숫자뽑기게임

BOJ 10468 숫자뽑기게임

[분류 - 다이나믹 프로그래밍]

 

[풀이]

  일차원 구간 다이나믹이다.
  이 문제의 핵심은 구간을 나눌 때 구간의 왼쪽과 구간의 오른쪽은 사용하지 않도록 구성하는 것이다. 즉, 구간의 가장 왼쪽과 가장 오른쪽은 사용하지 않도록 둔다.
  구간 사이에 있는 수들 중에서 하나(편의상 i번째)를 골라서 가장 마지막에 제거할 수(Number)로 둬보자. 그러면 그 수를 제외한 가장 왼쪽(l)과 그 수(i), 그리고 가장 오른쪽 수(r)가 남게 되는데 가장 왼쪽과 가장 오른쪽은 선택하지 않기로 했으므로 그 수를 뽑으면 점수는 k[l] + k[i] + k[r]가 추가 된다.
  이제 부분 문제는 어떻게 구성하냐면 가장 마지막에 뽑을 수가 i번째 수이므로 rec(l, i)는 왼쪽 구간을, rec(i, r)은 오른쪽 구간을 처리하도록 부분 구조를 구성하면 된다. 범위는 작아지고 똑같은 문제를 풀고 있음을 알 수 있다.

 

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX_N = 202;
int dp[MAX_N][MAX_N], n, k[MAX_N];
int rec(int l, int r) {
    int& ret = dp[l][r];
    if (ret != -1) return ret;
    ret = 0;
    for (int i = l + 1; i < r; i++)
        ret = max(ret, rec(l, i) + rec(i, r) + k[l] + k[i] + k[r]);
    return ret;
}
int main() {
    int ans, i, j;
    while (scanf("%d", &n)) {
        if (!n) break;
        memset(dp, -1, sizeof dp);
        for (i = 1; i <= n; i++) scanf("%d", &k[i]);
        k[n + 1] = 0;
        ans = 0;
        for (i = 1; i < n; i++) for (j = i + 1; j <= n; j++)
            ans = max(ans, rec(0, i) + rec(i, j) + rec(j, n + 1));
        printf("%d\n", ans);
    }
    return 0;
}