백준 1202 보석 도둑 / C++

문제 : 1202

풀이 point

그리디 + 트리 구조 multiset을 활용하는 문제이다.

풀이 방법

한 가방에는 한 보석만 담을 수 있다. 보석을 가격순으로 정렬한 후 가장 가격이 큰 보석부터 진행한다. 가장 가격이 큰 보석의 무게가 들어갈만한 가방 중 가장 크기가 작은 가방을 선택하여 넣는 것이 최대이다.

코드

//백준 1202, 보석 도둑

#include <iostream>
#include <set>
#include <algorithm>

std::pair<int, int> pair[300'000];
std::multiset<int> set;

int main (){

    int N, K;
    std::cin >> N >> K;
    for(int i{0}; i<N; ++i){
        std::cin >> pair[i].second >> pair[i].first;
    }
    std::sort(pair, pair+N);

    int k;
    for(int i{0}; i<K; ++i){
        std::cin >> k;
        set.insert(k);
    }

    long long ans = 0;

    for(int i{N-1}; i>=0; --i){
        int m, v;
        std::tie(v, m) = pair[i];
        auto it = set.lower_bound(m);
        if(it == set.end()) continue;
        ans += v;
        set.erase(it);
    }
    std::cout << ans;

    return 0;
}

2025-02-06T02:07:03.007Z