백준 1202 보석 도둑 (boj/1202.cpp)

그리디, 이진탐색을 엮은 문제입니다.

union-find의 find알고리즘을 조금 차용하여 구현했습니다.

보석이 들어갈 수 있는 가장 작은 가방을 찾은 다음, 그 가방보다 크기가 크거나 같고 && 비어있는 가방을 찾습니다. 이때 비어있다의 조건은 nxt[cur]==cur입니다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N, K;
vector< pair<int, int> > J;
vector< int > nxt;
vector< int > B;
int find(int cur){
    if(cur>=K || nxt[cur]==cur){ return cur; }
    return nxt[cur]=find(nxt[cur]);
}
void put(int cur){
    if(cur>=K){ return; }
    if(nxt[cur]==cur){ nxt[cur]=find(cur+1); }
    else{ put(nxt[cur]); nxt[cur]=find(nxt[cur]);  }
}
int bnsrc_S(int val){
    int lft=0, rht=K-1, mid;
    for(mid=(lft+rht)/2;lft<=rht;mid=(lft+rht)/2){
        if(mid==0){ return val>B[mid]; }
        if(B[mid-1]<val && val<=B[mid]){ return mid; }
        else if(val<=B[mid-1]){ rht=mid-1; }
        else{ lft=mid+1; }
    }
    return K;
}
int main(void){
    int M, V, C;
    int idx;
    long long sum;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin>>N>>K;
    J.resize(N); B.resize(K); nxt.resize(K);
    for(int i=0;i<N;i++){ cin>>M>>V; J[i]=make_pair(V, M); }
    for(int i=0;i<K;i++){ cin>>C; B[i]=C; nxt[i]=i; }
    sort(J.begin(), J.end()); sort(B.begin(), B.end());
    sum=0;
    for(int i=N-1;i>=0;i--){
        V=J[i].first; M=J[i].second;
        idx=bnsrc_S(M);
        if(idx>=K || find(idx)>=K){ continue; }
        sum+=V; put(idx);
    }
    cout<<sum;
    return 0;
}