백준 1202번 보석 도둑

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

 

두가지 접근 방법이 떠올랐는데
- 보석이 들어갈 수 있는 가장 작은 가방을 찾기

- 가방에 넣을 수 있는 최대 보석을 찾기
첫번째 방법은 시간초과가 발생하여서 두번째 방법으로 풀었다.

 

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

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

	// 변수 선언 및 초기화
	int n, k, m, v, c, idx = 0;
	long long sum = 0;
	cin >> n >> k;
	vector<pair<int, int>> gems(n);
	vector<int> bags(k);
	priority_queue<int> pq;

	// 입력, 무게로 정렬
	for (int i = 0; i < n; i++) {
		cin >> m >> v;
		gems[i] = { m, v };
	}
	for (int i = 0; i < k; i++) {
		cin >> c;
		bags[i] = c;
	}
	sort(gems.begin(), gems.end());
	sort(bags.begin(), bags.end());

	// 가방에 넣을 수 있는 최대 가격의 보석 찾기
	for (int bag : bags) {
		for (int i = idx; i < n; i++) {
			if (gems[i].first <= bag) {
				pq.emplace(gems[i].second);
				if (i == n - 1) idx = n;
			}
			else {
				idx = i;
				break;
			}
		}
		if (!pq.empty()) {
			sum += pq.top();
			pq.pop();
		}
	}

	cout << sum;

	return 0;
}

 

1. 보석과 가방은 무게순으로 정렬한다.

2. 가방을 순차적으로 넘어가며 넣을 수 있는 보석들의 가격을 우선순위큐에 넣는다.

3. 이때 보석의 진행도(idx)를 저장하여 다음에 이어서 넣는다.

4. 매 가방의 진행마다 우선순위큐에서 pop한 최대 가격의 보석을 sum에 합한다. (sum의 자료형 주의)