백준 1202 : 보석 도둑

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

1202번: 보석 도둑

 

이 문제는 보석을 전부 우선순위 큐에 넣어주고, 이분탐색으로 해당 보석을 넣을 수 있는 가방 중 가장 작은 것을 고르는 식으로, 우선순위큐 + 이분탐색으로 풀려고 했다가 시간초과로 실패하고 아래 블로그를 보고 공부했다.

 

https://jaimemin.tistory.com/760

백준 1202번 보석 도둑

 

풀이

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;
using pii = pair<int, int>;

int bag[300'000];
pii jw[300'000];
priority_queue<int> pq;

void solution() {
	int n, k, idx;
	long long sum = 0;
	
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> jw[i].first >> jw[i].second;
	}
	for (int i = 0; i < k; i++) {
		cin >> bag[i];
	}

	sort(jw, jw + n);
	sort(bag, bag + k);

	idx = 0;
	for (int i = 0; i < k; i++) {
    	//현재 가방이 수용할 수 있는 무게보다 작거나 같은
        //보석들을 전부 우선순위큐에 넣어준다.
		while (idx < n && jw[idx].first <= bag[i]) {
			pq.push(jw[idx].second);
			++idx;
		}
		
        //현재 우선순위큐에는 현재 가방에 들어갈 수 있는 보석들이
        //maxheap형태로 저장되어있으므로, 가장 value가 높은 보석을 가방에 담는다.
		if (!pq.empty()) {
			sum += pq.top();
			pq.pop();
		}
	}

	cout << sum << '\n';
}

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

	return 0;
}

메모리: 7204 kb

시간: 160 ms

 

보석이 아닌 가방을 기준으로 현재 가방에 들어올 수 있는 보석들을 우선순위 큐에 넣어 가장 큰 값을 고르는 식으로 문제를 해결함으로써 O(K + NlogN)의 시간복잡도로 해결 가능하다. (단, 1 <= N, K <= 300000)

 

반면 내가 처음 시도한 풀이는 아래의 코드인데, 사용한 가방을 처리하는 과정이 O(K)의 시간복잡도를 가지므로 최대 O(NK)의 시간복잡도를 가지므로 시간초과가 발생한다.

 

//************************ 틀린코드: 시간 초과 ****************************************

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

#define BOUND bag.begin(),bag.end()
using namespace std;
using pii = pair<int, int>;

vector<int> bag;
priority_queue<pii> pq;

void solution() {
	int n, k, m, v;
	long long sum = 0;

	cin >> n >> k;
	while (n--) {
		cin >> m >> v;
		pq.emplace(v, -m);
	}
	for (int i = 0; i < k; i++) {
		cin >> m;
		bag.push_back(m);
	}

	sort(BOUND);

	//pq는 value를 기준으로 내림차순, value가 같다면 무게를 기준으로 오름차순
	while (!pq.empty() && !bag.empty()) {
		v = pq.top().first, m = -pq.top().second;
		pq.pop();

		auto it = lower_bound(BOUND, m);
		//담을 수 있는 가방이 없는 경우
        	if (it == bag.end()) continue;
		sum += v;
		bag.erase(it);
	}

	cout << sum << '\n';
}

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

	return 0;
}