취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1202번 문제인 보석 도둑이다.
문제는 아래 링크를 확인하자.

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

담을 수 있는 무게가 적은 가방서부터 살펴보면서 그 가방에 담을 수 있는 가장 무거운 보석을 담는 것으로 이 문제를 해결할 수 있다.

이는 우선순위 큐에 현재 살펴보는 가방이 담을 수 있는 무게 이하의, 아직 담지 않은 보석들의 가격을 담아 관리하는 것으로 간단히 구현할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

struct query {
	int w, p;
	query(int w, int p) {
		this->w = w, this->p = p;
	}
};

bool comp(query q1, query q2) {
	if (q1.w != q2.w) return q1.w < q2.w;
	return q1.p > q2.p;
}

vector<query> q;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, K; cin >> N >> K;
	while (N--) {
		int w, p; cin >> w >> p;
		q.emplace_back(query(w, p));
	}
	while (K--) {
		int w; cin >> w;
		q.emplace_back(query(w, -1));
	}

	sort(q.begin(), q.end(), comp);
	
	ll ans = 0;
	priority_queue<int> pq;
	for (auto current : q) {
		if (current.p < 0) {
			if (pq.empty()) continue;
			ans += pq.top(); pq.pop();
		}
		else {
			pq.push(current.p);
		}
	}

	cout << ans;
}