보석 도둑

문제 링크

보석 도둑

아이디어

• \(N, K\) 의 범위를 고려하였을 때, \(O(NlogN)\) 이하의 시간 복잡도를 요구
• 고려해야하는 변수가 \(\textrm{(무게, 가치)}\)
  • 하나의 변인을 고정시킬 수 있을까?
• 결국, 하나의 보석이 담길 수 있는 가방들의 집합을 고려하였을 때 무게 변인을 고정시키는 방법을 고려
  • 보석, 가방을 무게를 중심으로 정렬
• 무게를 기준으로 정렬하였다면, 특정 가방에 담길 수 있는 보석들의 집합 중 가장 최대 가치를 가진 보석을 선택 (가방에는 최대1개의 보석이 담길 수 있으므로)
  • \(v_k\) 까지의 보석이 \(j\) 번 째 가방에 담길 수 있다면, \(v_{k+1}\) 부터의 보석은 \(j+1\) 번 째 가방부터 담길 수 있음
  • 💡 \(j+1\) 까지의 가방이 담을 수 있는 보석들의 집합은 \(j\) 까지에서 고려했던 보석들도 포함이 됨
• 최대 가치를 유지하기 위해서, 현재 가방에 담을 수 있는 보석들 중 최대 가치를 지닌 보석을 선택하는 방법을 택
• 모든 가방에 대해서 고려할 것이기 때문에, 각각의 가방에서 최대 가치를 지닌 보석을 선택하는 과정 은 \(\textrm{log}\) 타임을 요구
  • value를 기준으로하는 max heap tree 구성
• 무게를 중심으로 보석 또한 정렬되어 있기에, heap tree에 존재하는 모든 보석들은 다음 가방에도 적재할 수 있다는 것이 보장됨. (💡 참고)

소스코드

#include <bits/stdc++.h>
using namespace std;
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int N, K;
    cin >> N >> K;

    vector<pair<int,int>> v(N);
    for (int i = 0; i < N; i++) {
        int M, V;
        cin >> M >> V;
        v[i] = {M, V};
    }

    vector<int> bags(K);
    for (int i = 0; i < K; i++) {
        cin >> bags[i];
    }

    sort(v.begin(), v.end());
    sort(bags.begin(), bags.end());

    int idx = 0;
    long long answer = 0L;

    priority_queue<int, vector<int>> pq;
    for (int i = 0; i < bags.size(); i++) {
        while (idx < N && v[idx].first <= bags[i]) {
            // 현재 보석이 가방안에 담길 수 있음
            pq.push(v[idx].second);
            idx++;
        }
        if (!pq.empty()) {
            answer += pq.top();
            pq.pop();
        }
    }
    cout << answer;
    return 0;
}