[C++] BOJ-1202

 

문제풀이

---

1. pair<int, int>형 변수에 보석의 정보를 입력하고, backpack 변수에 가방의 정보를 입력한다.

 

2. 보석배열은 무게에 따라 정렬을 해주고 backpack 배열도 마찬가지로 정렬을 해준다.(오름차순)

 

3. 가방의 개수에 따라 반복문을 돌리는데 여기서 현재 선택된 가방에 넣을 수 있는 모든 보석의 가격을 우선순위큐에 집어넣습니다.

 

4. 그렇게 되면 우선순위 큐의 top에 위치한 보석이 현재 선택된 가방에 넣을 수 있는 보석 중 가장 비싼 보석이기 때문에 sum 변수에 더해주고 pop 해줍니다.

 

5. 위의 과정을 모든 가방에 대해서 반복합니다.

 

 

1시간 6분

 
#include <iostream>
#include <queue>
#include <algorithm>
 
using namespace std;
 
int N, K;
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> N >> K;
    
    priority_queue<int> pq;
    pair<int, int> jewer[N];
    int backpack[K];
    
    for(int i = 0; i<N; i++){
        cin>> jewer[i].first >> jewer[i].second;
    }
    
    for(int i = 0; i<K; i++){
        cin >> backpack[i];
    }
    
    sort(jewer,jewer+N);
    sort(backpack,backpack+K);
    
    long long sum = 0;
    int cnt = 0;
    
    for(int i = 0; i<K; i++){
        while(cnt < N && backpack[i] >= jewer[cnt].first){
            pq.push(jewer[cnt].second);
            cnt++;
        }
        
        if(!pq.empty()){
            sum += pq.top();
            pq.pop();
        }
    }
    
    cout << sum;
    
    return 0;
}