백준 1202 C++

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

이 문제 고민했던 점이 무게가 작은 보석부터 가방에 넣어야한다는 점을 인지하고 sort까진 했다.

근데 문제는 가격이었다. 

무게가 같은 것이라도 분명히 가격이 다른 것이 존재할 경우가 있다고 생각했다.

 

처음 생각한 것은 sort한 vector의 index를 올리면서 해당 보석을 넣고 안넣고 안들어가면 가방의 index를 높이는 방식이었다.

이건 n, k가 300,000이기 때문에 안될 것이라고 생각했다.

 

그 이후 가장 작은 가방에 들어갈 수 있는 보석은 다음 가방에도 들어갈 수 있다는 것이 떠올랐다.

그렇다면 priority_queue를 만들고 가격을 기준으로 정렬하면 된다.

 

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll n, k, result;	//보석, 가방 수
vector<pair<ll, ll>> j;
vector<ll> b;
priority_queue<ll> pq;

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

	cin >> n >> k;

	int w,p;
	for (int i = 0; i < n; i++) {
		cin >> w >> p;
		j.push_back({ w, p });
	}
	
	int bw;
	for (int i = 0; i < k; i++) {
		cin >> bw;
		b.push_back(bw);
	}

	sort(j.begin(), j.end());
	sort(b.begin(), b.end());

	int j_index=0;
	for (int i = 0; i < k; i++) {
		while (j_index < n && j[j_index].first <= b[i]) {		//j_index가 범위 안이면서 j_index에 해당하는 보석이 가방(b[i])에 들어갈 수 있다면
			pq.push(j[j_index].second);		//가격이 높은 순으로 정리해야하기 때문에 pq에 넣는다.
			j_index++;	//다음 보석이 b[i]라는 가방에 들어갈 수 있는지 확인한다.
		}

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

	cout << result;
}