[백준] 1202번 보석 도둑 (C++)

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

 

자료구조를 너무 그냥 처음부터 넣어놓고 꺼내면서 확인하는 식으로만 사용하려는 경향이 있는 것 같다. 고쳐야돼!! 유연한 사고!

 

먼저 이 문제도 O(N^2)을 최적화하는 문제이다. 그래서 처음에 생각했던 풀이는 이분탐색 lower bound이다. 단순히 이분탐색만 진행했다면 O(N long N)으로 가능하지만 안타깝게도 erase연산이 들어가야하기 때문에 O(N*K)와 다름없어지기 때문에 맞는 풀이가 아니다.

 

그래서 이 문제는 그리디 + 우선순위큐가 된다.

 

우선 가방의 크기대로 정렬하고 가방의 크기에 맞으면 전부 우선순위큐에 넣고 이제 더이상 못 넣으면 최댓값을 top으로 가져오면 된다.

 

이 생각만 해내면 쉬운데 생각하는게 힘들었다. 아무래도 생각의 흐름은 이렇게 됐어야할 것 같다.

 

1. O(N^2)로 하면 시간초과가 나니까 최적화를 해야겠다.

2. 결국 가방에는 하나만 넣을 수 있으니까 그 최댓값을 찾는데 우선순위큐를 사용해야겠다.

3. 우선순위큐에 넣어놓은 것들이 결국 이 다음에 다시 활용될 수 있겠네

4. 그래서 그리디하게 되는 건 모두 넣어도 괜찮겠다.

 

그러나 나는 2번에서 그 최댓값에 맞는 가방을 찾는 것으로 방향을 잘못잡아 문제를 풀지 못했다. 아이디어만 얻으면 구현은 쉬웠다.

 

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

vector<int> bags;
vector<pair<int, int>> gems;

priority_queue<int> pq;

int gemIdx = 0;
long long answer = 0;

void getMax(int bagSize){
    if(gemIdx == gems.size()) {
        if(!pq.empty()){
            answer += pq.top();
            //cout << "넣기 다참 : " << pq.top() << endl;

            pq.pop();
        }

        return;
    }

    while(gemIdx < gems.size()){
        int nowGemSize = gems[gemIdx].first;

        if(nowGemSize > bagSize){ // 이제 못담음
            if(!pq.empty()) {
                answer += pq.top();
                pq.pop();
            }

            return;
        }else{
            pq.push(gems[gemIdx].second);
            gemIdx++;
        }
    }

    if(!pq.empty()){
        answer += pq.top();
        pq.pop();
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

        gems.push_back({m, v});
    }

    for(int i = 0; i < K; i++){
        int b; cin >> b;
        bags.push_back(b);
    }

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


    for(int i = 0; i < K; i++){
        //cout << "가방" <<bags[i] << endl;
        getMax(bags[i]);
    }

    cout << answer << '\n';
}