[C++] 1202번 보석 도둑 - 그리디, 정렬, 우선순위 큐

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

#define MAX_BAG 300001
#define LOOP(i, n) for(int i=1; i<=n; i++)

using namespace std;

typedef long long int lld;

int N, K;  //보석 개수 N, 가방 개수 K
int b_wei[MAX_BAG];  //가방에 담을 수 있는 최대 무게. bag_weight
vector<pair<int, int>> jew;  //보석의 정보 M, V
lld sum;  //보석 가격의 합
priority_queue<int> pq;

void input()
{
    cin >> N >> K;
    LOOP(i, N) {
        int M, V;
        
        cin >> M >> V;
        jew.push_back({M, V});
    }
    LOOP(i, K) cin >> b_wei[i];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    input();
    
    sort(b_wei+1, b_wei+K+1);  //가방 오름차순 정렬
    sort(jew.begin(), jew.end());  //보석의 무게로 오름차순 정렬
    
    int id=0;
    LOOP(i, K) {
        int C = b_wei[i];
        
        for(; id<N && jew[id].first<=C; id++)
            pq.push(jew[id].second);
        if(!pq.empty()) {
            sum+=pq.top(); pq.pop();
        }
    }
    cout << sum;
    
    return 0;
}

솔직히 말해서 많이 어려웠다. 아마 그리디 알고리즘은 많이 접해보지 않아서 그런 것 같다. 그래도 그리디 알고리즘은 엄청 중요한 알고리즘이라서 공부해야하기는 한데... 시간을 두고 천천히 가보려고 한다. 

 

우선순위 큐의 사용법을 알게 된 것 같다. 우선순위 큐는 sort를 항시 유지하기 어려울 때 사용하는 것 같다. 우선순위 큐를 사용하는 것만으로 자동으로 sort를 해주니까. 

 

내 코드가 다른 사람 코드랑 똑같으면서도 8ms느린데 아마 매크로를 많이 써서 그렇지 않은가 싶다.

 

 

<우선순위 큐>

https://8156217.tistory.com/11

[C++] Priority Queue & Pair 사용법

 

 

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.