백준 g2 1202 보석 도둑 c++

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

1202번: 보석 도둑

 

문제

보석이 N개, 각 보석에 대해 무게 Mi와 가격 Vi가 주어진다.

상덕이의 가방이 K개, 각 가방이 담을 수 있는 최대 무게 Ci가 주어진다.

각 가방에는 보석을 1개만 담을 수 있다.

 

상덕이가 훔칠 수 있는 보석 가격 합의 최대는?

 

풀이(https://blog.encrypted.gg/1013)

그리디로 풀 수 있는 풀이

각 가방에는 보석을 하나만 담을 수 있다는 시점에서 최대 가격의 보석을 최대한 작은 무게의 가방에 넣는 것이 이득이라고 생각할 수 있다. 자세한 풀이는 위 링크 참고 .. 수학적 접근은 아직 나한텐 너무 어려움

 

수도 코드

보석 내림차순 정렬, 가방 오름차순 정렬

for 가장 가격이 큰 보석부터
	w = 그 보석의 무게
    가방 it = lower_bound(w)
    
    if w == set.end() // 값이 없으면
    	continue
    else
    	해당 가방 it 삭제 <-- //lower_bound를 계속 쓰려면 쓴 가방을 삭제해야 하므로
        		     //빈번한 삭제가 일어나는데 유리한 set사용
        answer += 보석 가치

 

사용한 가방은 삭제해야하므로, 삭제가 빠른 시간 안에 일어나고 lower_bound도 쓸 수 있는 set이 적합하다.

 

전체 코드

/*boj g2 1202 보석 도둑*/
#include <algorithm>
#include <iostream>
#include <set>
#define MAXN 300005
using namespace std;

int N, K;
pair<int, int> jewel[MAXN]; // 가격, 무게
multiset<int> bag;
long long answer;
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    // 0. input
    cin >> N >> K;
    for (int i = 0; i < N; i++) {
        int m, v;
        cin >> m >> v;
        jewel[i] = make_pair(v, m);
    }
    for (int i = 0; i < K; i++) {
        int c;
        cin >> c;
        bag.insert(c);
    }

    // 1. 정렬
    sort(jewel, jewel + N, greater<>());

    // 2. 가장 큰 보석부터 가능한 제일 작은 가방에 넣기
    for (int i = 0; i < N; i++) {
        int weight = jewel[i].second;
        auto it = bag.lower_bound(weight);

        if (it == bag.end()) { // 만족하는 가방이 없음
            continue;
        } else {
            bag.erase(it);
            answer += jewel[i].first;
        }
    }

    cout << answer << "\n";
}