백준 13058번 Jewel Thief

문제 요약

보석 도둑이 보석을 훔치려고 하는데 n개의 보석의 무게와 가치 $s_i, v_i$가 주어진다.

이 때, 사용할 수 있는 가방의 최대 무게 $k$가 주어지는데 무게가 1일 때 최대로 훔쳐갈 수 있는 보석의 최대 가치, 2일 때의 훔쳐갈 수 있는 보석의 최대 가치, ... , k일 때 훔쳐갈 수 있는 보석의 최대 가치를 계산해야 한다.

n은 최대 100만이며, k는 최대 10만이다.

그리고 보석이 가질 수 있는 무게는최대 300이며, 가치의 범위는 최대 $10^9$이다.

풀이

먼저, 무게가 같은 보석들을 모아놓고 가치에 대한 내림차순으로 정렬을 한다.

그 다음에 다음과 같은 dp식을 생각해보자.
$$
dp(g, k) = \text{1부터 g까지의 무게들을 가진 보석만으로 크기 k 가방을 채웠을 때 최대가치}
$$
이렇게 dp식을 세웠으면 아래와 같은 점화식이 나온다.
$$
dp(g,k) = \underset{i<k/g}{max}(dp(g-1,k-ig)+C(g,k))
$$
여기서 $C(i,k)$는 무게 $g$인 보석들을 $k$개 골랐을 떄의 최대 가치를 뜻한다.

여기까지 오면 이 문제는 BOJ 16138번 수강신청 문제와 수의 범위만 조금 다른 문제가 된다. 같은 풀이를 적용해서 풀 수 있다. 풀이 링크

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = -1e18;
vector<vector<ll>> a(301);
int N, K;
ll dp[305][100005];
vector<vector<ll>> pre_sum(301);

void solve(int w, int s, int e, int opts, int opte, int offset) {
    if(s > e) return ;
    int mid = (s+e) >> 1;
    ll &ans = dp[w][mid*w+offset];
    ans = INF;
    int opt_mid = opte;
    for(int i=opts;i<=min(mid, opte);++i) {
        if(mid-i > a[w].size()) continue;
        ll tmp = dp[w-1][i*w+offset] + pre_sum[w][mid-i];
        if(ans < tmp) {
            ans = tmp; opt_mid = i;
        }
    }
    solve(w, s, mid-1, opts, opt_mid, offset);
    solve(w, mid+1, e, opt_mid, opte, offset);
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N >> K;
    for(int i=0;i<N;++i) {
        ll s, v;
        cin >> s >> v;
        a[s].push_back(v);
    }
    for(int i=1;i<=300;++i) sort(a[i].begin(), a[i].end(), [] (int a, int b) { return a > b; });
    for(int i=1;i<=300;++i) {
        pre_sum[i].push_back(0);
        for(int j=1;j<=a[i].size();++j) {
            pre_sum[i].push_back(pre_sum[i][j-1] + a[i][j-1]);
        }
    }
    for(int i=1;i<=300;++i) {
        for(int j=0;j<i;++j) {
            solve(i, 0, (K-j)/i, 0, (K-j)/i, j);
        }
   }
   vector<ll> ans(K+1, 0);
   for(int i=1;i<=300;++i) for(int j=1;j<=K;++j) ans[j] = max(ans[j], dp[i][j]);
   for(int i=1;i<=K;++i) cout << ans[i] << " \n"[i==K];
   return 0;
}