BOJ)2419 사수아탕

문제:icpc.me/2419

사탕이 담긴 사탕바구니가 x축위에 있고 1초마다 사탕 바구니의 사탕이 1개씩 사라질 때 수아가 먹을 수 있는 최대의 사탕 수를 구하는 문제이다.

문제가 다이나믹 프로그래밍임은 쉽게 알 수 있었지만 먹을 수 있는 최대의 사탕수에 포커스를 맞추니 어려워진 문제였다.

이를 dp[l][r][state]로 해결해야하는데 l에서 r까지 사탕을 커버하고 state(왼,오)에 서있을 때 먹는 최대의 사탕수라고 

정의를 한 뒤 제출을 하니까 WA를 받았다. 다시 잘 생각해보니 l~r을 커버할 때 나머지 구간에 사라진 사탕수가 항상 최적으로 있을 수 없다는 걸 깨달았다.

따라서 dp테이블의 정의를 바꾸어 l에서 r까지 구간을 커버하고 사라지는 사탕 수로 문제를 풀어야한다.

근데 이 또한 사라지는 사탕수를 계산하기 어려워지기 때문에 먹을 사탕 K를 정해놓고 모든 k에 대하여 답을 구해보면 된다.

K를 정한다면 예를 들어 현재 먹을 사탕이 k개 남았고 l~r까지 커버하고 r에서 r+1로 이동한다면 (a[r+1]-a[r])*k 개의 사탕이 사라질것이다.(이동하는 동안 앞으로 먹을 나머지 k개의 사탕이 사라지기 때문)

이를 이용하여 점화식을 세워준 뒤 풀면 된다.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
int n, dp[333][333][2], x, m, res;
vector<int> v;
int func(int l, int r, int state, int rem) {
    if (!rem)return 0;
    if (l > r)return 1e9;
    int &ret = dp[l][r][state];
    if (ret != -1)return ret;
    ret = 1e9;
    if (state) {//왼
        if (r != n)
            ret = min(ret, func(l, r + 1, 0, rem - 1) + rem*(v[r + 1] - v[l]));
        if (l)
            ret = min(ret, func(l - 1, r, 1, rem - 1) + rem*(v[l] - v[l - 1]));
    }
    else {//오
        if (r != n)
            ret = min(ret, func(l, r + 1, 0, rem - 1) + rem*(v[r + 1] - v[r]));
        if (l)
            ret = min(ret, func(l - 1, r, 1, rem - 1) + rem*(v[r] - v[l - 1]));
    }
    return ret;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        v.push_back(x);
    }
    v.push_back(0);
    sort(v.begin(), v.end());
    memset(dp, -1, sizeof(dp));
    int idx = lower_bound(v.begin(), v.end(), 0) - v.begin();
    for (int i = 0; i <= n; i++) {
        memset(dp, -1, sizeof(dp));
        res = max(res, i*m - func(idx, idx, 0, i));
    }
    printf("%d\n", res);
    return 0;
}