[BOJ] 보석 도둑 1202번 C++

문제

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

 

접근 방식

 

보석의 무게와 가격을 함께 저장하고 보석을 가격 순으로 정렬한다

그리고 가격이 높은 순으로 가장 자신의 무게와 비슷한 가방에 넣는다!

가방은 c++ STL인 multiset을 이용하면 쉽게 관리할 수 있다

multiset은 중복이 허용한 set 자료구조로 c++에서는 정렬 기능까지 함께 제공해준다

 

즉, 보석을 가격순으로 정렬하고

가방에 넣을 건데 lower_bound 메소드를 사용해서

보석의 무게보다 크거나 같지만  그 중에서 가장 작은 값을 찾을 수 있다

 

코드

#include<bits/stdc++.h>
using namespace std;

vector<pair<int,int>> values;
multiset<int> bags;

int main() {
    int N,K; cin>>N>>K;
    for(int i=0; i<N; i++) {
        int m,v; cin>>m>>v;
        values.push_back(make_pair(v,m));
    }
    for(int i=0; i<K; i++) {
        int x; cin>>x;
        bags.insert(x);
    }

    sort(values.begin(), values.end());

    long long ans = 0;

    for(int i=N-1; i>=0; i--) {
        auto it = bags.lower_bound(values[i].second);
        if(it == bags.end()) continue;

        ans += values[i].first;
        bags.erase(it);
        
    }
    cout<<ans;


}

 

간단해보이지만 쉽지 않았던 문제다..