백준 1202 (보석 도둑)

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

1202번: 보석 도둑

가방이 K개 존재하고, 그 가방에 보석을 단 하나만 담을 수 있다. 

그리고 가방에 제한이 있는데 무게 제한이 있고, 보석은 무게와 가치를 가지고 있다. 

 

접근은 간단하다고 생각한다. 

 

그리디하게 보석을 가치 순으로 정렬하고, 그 가치 순서대로 가방에 넣으면 된다.

 

우리가 그 전에 풀어왔던 냅색 dp와 달리 가방에는 단 하나의 보석만 들어갈 수 있으므로,

어떤 가방에 보석이 들어간다면 그 보석의 가치가 가장 큰 걸 넣으면 된다. 이는 자명하다. 

 

막무가내로 넣으면 될까? 아니다. 

 

어떤 보석을 넣을 수 있는 최소 무게 가방을 사용한다. 

 

이는 그냥 가방을 정렬하고, 이분탐색해서 찾는다. 

그런데 문제가 있다. 찾고 삭제해야하는데 

 

위 과정이 모든 보석에 대해서 실행되므로 삭제가 O(N)보다 작은 O(logN) 크기의 자료구조가 필요하다.

아마도 multi set으로 되지 않을까 생각한다. 

 

나는 멀티셋이 생각나지 않아서 연결리스트를 구현하였다. 

 

vector erase의 시간복잡도는 O(N)이다. 

 

 

------------------------------------------------------------------------------------------------------------------

자료구조 우선순위 큐만 사용해서 어떤 가방에 들어갈 수 있는 보석 중 가치 최고를 제외하는 식으로 푸는 것도 가능하다. 이는 좀 더 어려운 아이디어인것 같다. 

 

#include <bits/stdc++.h>

using namespace std;
#define TEST int tt; cin >> tt; while (tt--)
#define all(v) (v).begin(), (v).end()
#define loop(e, v) for (auto& (e) : (v))
#define mem(v, e) memset((v), (e), sizeof(v))
#define _unique(v) (v).erase(unique((v).begin(),(v).end()),(v).end())
#define pii pair<int, int>
#define pll pair<ll, ll>
#define tii tuple<int, int, int>
#define tll tuple<ll, ll, ll>
#define xx first
#define yy second
#define ll long long
#define ld long double
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(0);
const int MAX = 1'000'005;
const int INF = 1e9 + 1;
const ll LINF = 1e18;
const ll MOD = 1e9 + 7;

vector<pii> v;
vector<pii> bo(MAX+1);

bool compare(pii a, pii b){
    if(a.first != b.first)return a.first > b.first;
    else return a.second < b.second;
}

int find_index(int n){
    if(bo[n].second) return n;
    return find_index(bo[n].first);
}

int main() {
    FASTIO
    int N, K;
    cin >> N >> K;
    for(int i=0; i<N; i++){
        int a, b;
        cin >> a >> b;
        v.push_back({b,a});
    }
    for(int i=0; i<K; i++){
        int a;
        cin >> a;
        bo[a].first = a;
        bo[a].second++;
    }
    int before = MAX;
    bo[MAX].first = MAX;
    bo[MAX].second = 1;
    for(int i=MAX; i>=0; i--){
        if(bo[i].second==0)bo[i].first = before;
        else before = i;
    }
    sort(all(v), compare);
    ll ans = 0;
    for(auto a : v){
    //    cout << a.first << " " << a.second << '\n';
        int b = find_index(a.second);
        if(b==MAX)continue;
        bo[b].second--;
        if(!bo[b].second){
            bo[a.second].first = bo[b].first = find_index(b+1);
        }
        ans+=a.first;
        K--;
        if(!K)break;
    }

    cout << ans;
}