[백준] 1202번 보석 도둑

1202 보석도둑

문제

---

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

상덕이가 털 보석점에는 보석이 총 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)

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

출력

---

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

---

풀이)

greedy 문제이다.

"무게가 낮은 가방부터 최대한 가격 높은 보석을 넣는다" 가 핵심 point다.

과정

1. 보석을 무게순으로 정렬해놓는다. (무게 낮은 순 -> 무게 높은 순)

2. 가방을 무게순으로 정렬해놓는다. (무게 낮은 순 -> 무게 높은 순)

3. 가방 개수만큼 반복문을 돌린다.

  3.1 i번째 가방 무게보다 가벼운 보석들의 가격을 모두 PQ에 넣는다.

  3.2 PQ의 top 값을 결과값에 더한다.

       (PQ는 내림차순으로 가격이 높은 순에서 -> 낮은 순으로 정렬해준다. 

  따라서 top값을 더한다면 그것은 곧 현재 가방무게보다 가벼우며, 

    가격이 가장 높은 보석을 그 가방에 넣어주는 것이다.)

주의사항

1. 결과값의 자료형을 int로 선언하면 안된다.

   가격의 최대값 300,000 * 가방의 개수 1,000,000 = 300,000,000,000

   *int형의 범위를 넘어갈 수 있다.*

   (이를 간과해 여러번 틀렸다.)

2. 보석을 가격(높->낮), 무게(낮->높) 순으로 정렬하고

    PQ가 아닌 이중 포문으로 돌리면 시간초과가 난다. 

시간초과 코드.

bool cmp(const pair<int, int> &a, const pair<int, int> &b) {

if (a.first == b.first) return a.second < b.second;

return a.first > b.first;

}

...

      sort(jew.begin(), jew.end(), cmp);

...

for (int i = 0; i < K; i++) {

for (int j = 0; j < jew.size(); j++) {

if (jew[j].first == -1) continue;

if (jew[j].second <= weight[i]) {

result += jew[j].first;

jew[j].first = -1;

break;

}

}

}

코드)

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
 
int N, K, M, V, C;
vector<int> weight;
vector<pair<int, int>> jew;
 
int main() {
    scanf("%d %d", &N, &K);
    for (int i = 0; i < N; i++) {
        scanf("%d %d", &M, &V);
        jew.push_back({ M,V });
    }
 
    for (int i = 0; i < K; i++) {
        scanf("%d", &C);
        weight.push_back(C);
    }
    //보석 : 무게(낮->높) 순
    sort(jew.begin(), jew.end());
    //가방 : 무게(낮->높) 순
    sort(weight.begin(), weight.end());
    long long result = 0; //300,000 * 1,000,000
    int i = 0, j = 0;
    priority_queue <int> qu; //priority_queue는 내림차순, 가격순으로
 
    //무게가 낮은 가방부터 최대한 가격이 높은 보석을 넣음
    for (int i = 0; i < K; i++) {
        while (j < N) {
            if (jew[j].first <= weight[i]) {
                qu.push(jew[j].second);
                j++;
            }
            else break;
        }
        if (!qu.empty()) {
            result += qu.top();
            qu.pop();
        }
    }
 
    printf("%lld\n", result);
    return 0;
}