https://www.acmicpc.net/problem/1093

설명

간단히 하자면, 스티커의 부분 집합의 가치를 $K$이상으로 할 때, 드는 돈의 최소값을 구하는 것이다. 이 문제에서는 스티커의 판매 가격과 구매 가격이 동일하기 때문에, 지금 가지고 있는 스티커를 전부 돈으로 바꿔도 전혀 문제가 되지 않는다.

이 문제에서 스티커의 개수는 최대 32개이기 때문에 모든 경우의 수를 다 체크하는 Brute Force를 생각해 볼 수 있겠다. 전체를 다 살펴보는 것은 TLE를 받기 때문에 스티커 집합을 반으로 쪼갠 다음, 그 집합 안에서 전체 경우의 수를 세자. 이때 전체 경우의 수는 최대 $2^{16}$이기에 충분히 다 탐색할 수 있다.

탐색이 끝났다면, 한쪽을 lower_bound를 쓰기 위해 가치를 기준으로 정렬하자. 그리고 정렬된 경우의 수들을 뒤에서부터 탐색하면서, 나보다 큰 가치를 지니지만, 가격은 더 싼 경우의 수의 가격으로 업데이트한다. 어차피 가치는 $K$를 넘는 것만이 중요하기에, 가치가 넘치는 것은 상관이 없기 때문이다.

이후 정렬하지 않은 경우의 수를 순회하면서 lower_bound를 사용하여 가격을 구한 뒤, 최소값인지 확인하면서 업데이트하면 된다. 마지막에 최소값에 원래 들고 있던 스티커의 가격을 빼줌으로서, 답을 구할 수 있다.

코드

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;

vector<int> P,V;
vector<pll> L,R; //{가격,가치};
ll K,sum;
int N,C;

bool compare(pll a,pll b) {
    if(a.second == b.second) return a.first < b.first;
    return a.second < b.second;
}

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    cin >> N;
    V.resize(N), P.resize(N);
    for(int i=0; i<N; i++) cin >> P[i];
    for(int i=0; i<N; i++) cin >> V[i];
    cin >> K >> C;
    for(int i=0; i<C; i++) {
        int temp;
        cin >> temp;
        sum += P[temp];
    }

    int left = N/2, right = N - left;
    L.resize(1<<left), R.resize(1<<right);
    for(int i=0; i<(1<<left); i++) {
        pll ret = {0,0};
        for(int j=0; j<left; j++)
            if((i>>j)&1) ret.first += P[j], ret.second += V[j];
        L[i] = ret;
    }
    for(int i=0; i<(1<<right); i++) {
        pll ret = {0,0};
        for(int j=0; j<right; j++)
            if((i>>j)&1) ret.first += P[left+j], ret.second += V[left+j];
        R[i] = ret;
    }

    sort(R.begin(),R.end(),compare);
    for(int i=(1<<right)-2; i>=0; i--)
        R[i].first = min(R[i].first,R[i+1].first);

    ll ret = 0x7FFFFFFF;
    for(auto tt : L) {
        ll price = tt.first, val = tt.second;
        auto it = lower_bound(R.begin(),R.end(),make_pair(0,K-val),compare);
        if(it != R.end()) ret = min(ret,price + it->first);
    }
    if(ret == 0x7FFFFFFF) cout << -1;
    else cout << max(ret-sum,0LL);
}

여담

$N$이 작은 경우는 다 탐색할 수 있는지 살펴보는 것도 중요한 것 같다.