[Baekjoon/C++] 1202번 - 보석 도둑

[백준] Baekjoon Online Judge

문제로 이동

 

문제

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

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

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

 

출력

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

 

---

풀이

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

struct Jewel {
    int weight = 0; // 무게
    int price = 0;  // 가격
};

int N, K, now = 0;
Jewel jewel[300001];
int bag[300001];
priority_queue<pair<int, int>> canPut;

bool compare(Jewel a, Jewel b);
int putJewel(int bag);

bool compare(Jewel a, Jewel b) {
    if (a.weight == b.weight) return a.price > b.price;
    return a.weight < b.weight;
}

int putJewel(int bag) {
    while (true) {
        if (now >= N) break;

        if (jewel[now].weight > bag) break;

        canPut.push({ jewel[now].price, jewel[now].weight });
        now++;
    }

    if (canPut.empty()) return 0;
    else {
        int result = canPut.top().first;
        canPut.pop();

        return result;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> K;
    for (int i = 0; i < N; i++) {
        int m, v;
        cin >> m >> v;

        jewel[i] = { m, v };
    }

    for (int i = 0; i < K; i++) cin >> bag[i];

    sort(jewel, jewel + N, compare);
    sort(bag, bag + K);

    long long result = 0;
    for (int i = 0; i < K; i++) result += putJewel(bag[i]);

    cout << result << '\n';

    return 0;
}

 각 가방에는 1개의 보석만을 챙길 수 있으므로 각 가방에 들어갈 수 있는 보석 중 가장 비싼 것을 선택하면 된다.

 

bool compare(Jewel a, Jewel b) {
    if (a.weight == b.weight) return a.price > b.price;
    return a.weight < b.weight;
}

 보석을 크기별로 정렬하기 위해 구현한 함수이다.

 

int putJewel(int bag) {
    while (true) {
        if (now >= N) break;

        if (jewel[now].weight > bag) break;

        canPut.push({ jewel[now].price, jewel[now].weight });
        now++;
    }
	
    // 보석이 없는 경우
    if (canPut.empty()) return 0;
    else {
        int result = canPut.top().first;
        canPut.pop();

        return result;
    }
}

 가방에 넣을 수 있는 가장 비싼 보석을 선택하는 함수이다. 우선순위 큐에 해당 가방에 들어갈 수 있는 모든 보석을 while문으로 넣으면 top에는 가장 비싼 보석이 위치하게 된다. 이때 이전 가방에 넣지 않았던 보석은 다음으로 작은 가방에도 들어갈 수 있으므로 큐의 내용물을 유지하고, 중복을 피하기 위해서 전역변수를 사용하였다. 보석이 하나도 없다면 0을, 있다면 보석의 가치를 return하게 된다.