이번에는 백준 1202번 보석 도둑 문제를 풀어보았습니다.
문제를 처음 봤을 때 각 가방에 들어갈 수 있는 보석 중 가장 비싼 것을 선택하면 된다고 생각했습니다.
하지만 모든 가방마다 모든 보석을 확인하면 시간 초과가 발생합니다.
그래서 가방과 보석을 모두 무게 기준으로 정렬한 뒤, 현재 가방에 들어갈 수 있는 보석들만 우선순위 큐에 넣고 가장 가치가 높은 보석을 선택하는 방식으로 구현하였습니다.
문제 설명
각 보석은
- 무게
- 가격
을 가지고 있습니다.
각 가방에는 최대 한 개의 보석만 담을 수 있으며, 가방마다 최대 무게가 정해져 있습니다.
훔칠 수 있는 보석 가격의 합의 최댓값을 구하는 문제입니다.
풀이 아이디어
먼저 가방을 무게 기준으로 오름차순 정렬하였습니다.
보석 역시 무게 기준으로 오름차순 정렬하였습니다.
현재 가방에 들어갈 수 있는 모든 보석을 우선순위 큐에 넣었습니다.
우선순위 큐에는 보석의 가격만 저장하였고, 가장 가격이 높은 보석이 먼저 나오도록 최대 힙을 사용하였습니다.
각 가방마다 가장 가치가 높은 보석을 하나 선택하여 정답에 더하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N,K;
vector<int> bag;
vector<pair<int, int>> treasure;
cin >> N >> K;
for (int i=0; i<N; i++) {
int w,v;
cin >> w >> v;
treasure.push_back({w,v});
}
for (int i=0; i<K; i++) {
int w;
cin >> w;
bag.push_back(w);
}
sort(bag.begin(), bag.end());
sort(treasure.begin(), treasure.end());
priority_queue<int> pq;
long long int ret = 0;
int idx = 0;
for (int next_bag : bag) {
while (idx < N && treasure[idx].first <= next_bag) {
pq.push(treasure[idx].second);
idx++;
}
if (!pq.empty()) {
ret += pq.top();
pq.pop();
}
}
cout << ret << '\n';
return 0;
}풀이 흐름
- 가방을 무게 기준으로 정렬합니다.
- 보석을 무게 기준으로 정렬합니다.
- 현재 가방에 들어갈 수 있는 모든 보석을 우선순위 큐에 넣습니다.
- 우선순위 큐에서 가장 가치가 높은 보석을 선택합니다.
- 모든 가방에 대해 반복합니다.
- 선택한 보석 가격의 합을 출력합니다.
구현 포인트
1. 가방과 보석 정렬
가방과 보석을 모두 무게 기준으로 오름차순 정렬하였습니다.
sort(bag.begin(), bag.end());
sort(treasure.begin(), treasure.end());가방을 작은 것부터 처리하면서 넣을 수 있는 보석을 차례대로 확인하도록 구현하였습니다.
2. 현재 가방에 들어갈 수 있는 보석 추가
현재 가방의 무게 이하인 보석만 우선순위 큐에 넣었습니다.
while (idx < N && treasure[idx].first <= next_bag) {
pq.push(treasure[idx].second);
idx++;
}한 번 확인한 보석은 다시 확인할 필요가 없으므로 idx를 계속 증가시키며 관리하였습니다.
3. 최대 힙 사용
우선순위 큐에는 보석의 가격만 저장하였습니다.
priority_queue<int> pq;현재 가방에 담을 수 있는 보석들 중 가장 가치가 높은 보석을 빠르게 선택할 수 있습니다.
4. 가장 가치가 높은 보석 선택
현재 가방에 담을 수 있는 보석이 있다면 가장 가치가 높은 보석을 선택하였습니다.
if (!pq.empty()) {
ret += pq.top();
pq.pop();
}선택한 보석은 다른 가방에서 사용할 수 없으므로 제거하였습니다.
5. 한 번만 순회
보석은 무게순으로 정렬되어 있기 때문에 idx는 한 번만 증가합니다.
int idx = 0;각 보석은 우선순위 큐에 한 번만 들어가고 한 번만 제거되므로 전체 시간복잡도는
O((N + K) log N)으로 해결할 수 있었습니다.
