[백준 1202] 보석 도둑

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

 

1. 문제 이해

가방을 돌면서 보석의 우선순위에 따라 가격을 더해줌 !

주얼리는 무게가 작고, 가격이 쎈 순서대로 정렬해주고,

가방은 오름차순으로 정렬해주었다.

 

idx는 이미 더해준 값은 보지 않기 위한 인덱스이다.

pq는 무게가 작은 것 중 제일 쎈 가격이 나오도록 선언해주었다.

처음에는 else break;를 해주지 않아 300,000 * 300,000으로 시간초과가 났다

꼭 선언해주기 !

(힌트는 도움이 안됐다 .. 가방을 내림차순해야하는 줄 알았다ㅠ)  

 

2. 구현

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

int n, k, m, v, c;
vector<pair<int, int>> jewel;
vector<int> bag;
long long result = 0;

bool cmp(pair<int, int> a, pair<int, int> b) {
    if (a.first == b.first) {
        return a.second > b.second;
    }
    return a.first < b.first;
}

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

    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> m >> v;
        jewel.emplace_back(m, v);
    }
    for (int i = 0; i < k; i++) {
        cin >> c;
        bag.push_back(c);
    }
    sort(jewel.begin(), jewel.end(), cmp);
    sort(bag.begin(), bag.end());

    int idx = 0;
    priority_queue<int> pq;

    for (int i = 0; i < k; i++) {
        int bag_size = bag[i];

        for (int j = idx; j < n; j++) {
            if (jewel[j].first <= bag_size) {
                pq.push(jewel[idx].second);
                idx++;
            } else {
                break; //중요
            }
        }
        if (!pq.empty()) {
            result += pq.top();
            pq.pop();
        }
    }
    cout << result;

    return 0;
}