백준 1202 - 보석 도둑(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1202

1202번: 보석 도둑

까다로운 그리디 문제였습니다.

보석을 어떤 순으로 담아야 되는지 생각했어야 했습니다.

N과 K의 범위가 300,000 이기에 가방 한개마다 모든 보석을 확인하기에는 문제가 있습니다.

따라서 우선순위 큐를 사용했습니다.

우선순위 큐를 사용하면 조건에 따라 가장 작은 or 가장 큰 값이 루트에 있기에 이를 가져오기만 하면 됩니다.

 

먼저, 보석과 가방을 무게에 따라 오름차순 정렬을 해줬습니다.

가방의 무게까지 우선순위 큐에 모든 보석을 넣어주면, 루트에 가방 무게에서 넣을 수 있는 가장 큰 가치의 보석을 찾을 수 있습니다.

 

이를 모든 가방까지 반복해주면 됩니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <stack>
#include <map>
#define LL long long
#define pp pair<int, int>
#define F first
#define S second

using namespace std;

int N, K;
vector<pp> ruby;
vector<int> weight;
priority_queue<int> q;

bool cmp(pp a, pp b){
    if(a.F < b.F) return true;
    else if(a.F == b.F){
        if(a.S < b.S) return true;
        else return false;
    }
    else return false;
}

void solve(){
    sort(ruby.begin(), ruby.end(), cmp);
    sort(weight.begin(), weight.end());
    long long ans = 0;
    int idx = 0;
    for(int i = 0; i < K; i++){
        while(1){
            if(idx >= N) break;
            if(ruby[idx].F > weight[i]) break;
            q.push(ruby[idx].S);
            idx++;
        }
        if(!q.empty()){
            ans += q.top();
            q.pop();
        }
    }
    cout << ans;
}

int main() {
    cin.tie(0);
	cout.tie(0);
	cin >> N >> K;
	for(int i = 1; i <= N; i++){
	    int x, y;
	    cin >> x >> y;
	    ruby.push_back({x, y});
	}
	for(int i = 1; i <= K; i++){
	    int x;
	    cin >> x;
	    weight.push_back(x);
	}
	solve();
	return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요