BOJ 1202. LOPOV

문제 링크

 

문제 풀이

 이 문제는 $N\leq 3\times 10^5$개의 보석과 $K\leq 3\times 10^5$개의 가방이 주어지고, 각 보석의 무게 $M_{i}$, 가격 $V_{i}$와 가방에 담을 수 있는 최대 무게 $C_{i}$가 주어질 때 담을 수 있는 보석의 최대 가격을 출력하는 문제이다. 

 

 일단 당연히 최대 가격을 얻기 위해선 보석들 중 가격이 높은 순서대로 가방에 넣는 것을 시도해야 한다. 그래서 그리디 알고리즘으로 생각해보면 가격이 높은 보석들부터 가방에 넣는데, 그 가방의 무게는 보석의 무게를 넘는 최소의 무게(lower bound)일 수록 좋을 것이다. 만약 만족하는 가방이 없거나 이미 보석을 넣은 상태라면 넣지 못할 것이다. 이렇게 생각하면 일단 보석에 대해 iteration을 할 때, $O(N)$이고 여기서 가방을 찾는데 $O(logK +K)$이므로 $O(N(K+logK))$의 자명한 풀이를 얻을 수 있다. 이건 당연히 시간초과가 난다.

 

 그래서 가방을 찾는데 $O(logK)$만 걸리도록 수정을 할 생각을 했다. $O(K)$가 추가로 걸리는 이유는 lowerbound로 찾은 가방에, 이전에 보석이 넣어져서 다음 가방을 탐색해야하는 경우가 발생하면 최악에 경우 $K-1$번 다른 가방을 확인해야하기 때문이다. 그래서 각 가방에, 다음 가방으로 가능한 가방에 대한 정보를 추가적으로 저장해주면 $O(1)$만에 확인할 수 있을 것이다.

 

pair<long long, int> Bag[KMAX];

 

 그래서 가방을 저장하는 배열을 pair로 만들었는데 앞에 long long부분이 가방의 최대 무게이고, 뒤에 int부분이 다음 가방의 번지수이다. 보석이 들어있는 않는 경우는 int부분이 자신의 번지수로 설정되어있을 것이다.

 추가적으로 $O(1)$으로 근사시키기 위해 경로 압축을 이용할 수 있다. 

 

 전체적으로 시간복잡도를 구해보면 $O(NlogK)$로 근사된다.

 

 

 

 

시행착오

$\cdot$ long long으로 안해놔서 오버플로우가 발생한 거 같다.

$\cdot$ 경로 압축을 안해줘서 TLE를 받았다.

 

 

 

 

코드

#include <iostream>
#include <algorithm>
using namespace std;
#define KMAX 300000
#define NMAX 300000
typedef long long ll;

ll N,K,MXPRICE=0;
pair<ll,ll> Jewel[NMAX];
pair<ll, int> Bag[KMAX];
ll Bag1[KMAX];

void input(){
    cin>>N>>K;
    for(int i=0;i<N;i++){
        ll m,v;
        cin>>m>>v;
        Jewel[i] = {v,m};
    }
    for(int i=0;i<K;i++){
        ll C;
        cin>>C;
        Bag[i] = {C,0};
    }
}

void init(){
    sort(Bag,Bag+K);
    sort(Jewel,Jewel+N,greater<pair<ll,ll>>());
    for(int i=0;i<K;i++){
        Bag[i].second = i;
        Bag1[i] = Bag[i].first;
    }
}

int find(int x){
    if(x==-1||x==Bag[x].second) return x;
    return Bag[x].second = find(Bag[x].second);
}
void solve(){
    for(int i=0;i<N;i++){
        ll V = Jewel[i].first;
        ll M = Jewel[i].second;
        int lb = lower_bound(Bag1,Bag1+K,M) - Bag1;
        if(Bag[lb].first<M) continue;
        int k = find(lb);
        if(Bag[k].first<M||k == -1) continue;
        MXPRICE += V;
        if(k==K-1) Bag[k].second = -1;
        else Bag[k].second = Bag[k+1].second;
    }
}

void output(){
    cout<<MXPRICE;
}

int main(){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    input();
    init();
    solve();
    output();
}