🔵 문제 링크
https://www.acmicpc.net/problem/1202
🔵 문제 설명
논리적인 식을 세우는 문제는 아닌 것 같고 최적의 해가 나올 것 같은 상황을 가정해서 그리디하게 풀어야 한다.
내가 생각했을 때 최적의 해가 나올 것 같은 상황은 다음과 같다.
최대한 제일 비싼 보석들을 훔쳐야 한다.
근데 보석마다 무게가 정해져 있는데, 이 보석을 가방에 넣을 때, 최대한 보석의 무게와 같아야 한다.
비싸고 가벼운 보석을 무게 용량이 큰 가방에 넣어버렸다고 가정하자.
다른 마땅한 보석이 나오면 그 보석의 무게에 맞는 가방이 없을 수도 있기 때문이다. (가방에는 보석 하나만 넣을 수 있기 때문.)
🔵 시도 1 이중 포문
이런 가정을 코드로 구현하여 무식하게 이중 포문을 돌려 보았다. (안 된다는 것을 알면서도...)
하지만 시간 초과가 나왔다.
당연하다.
입력이 최대 30만인데, 이중 포문을 돌면 제한 시간인 1초를 훌쩍 넘어버리기 때문이다.
🔵 시도 2 lower_bound와 multiset을 이용
multiset과 lower_bound라는 것을 알게 되었다.
이 풀이는 보석을 기준으로 담을 수 있는 가장 작은 가방을 찾는 풀이이다.
🔷 multiset
- 중복을 허용하는 정렬된 컨테이너이다.
- 내부적으로 red-black tree로 구현되어 있어 항상 정렬된 상태를 유지한다.
- 삽입/삭제 시간은 O(log N)만큼 걸린다.
🔷 lower_bound
- 정렬된 컨테이너에서 사용 가능하다.
- lower_bound(x)는 x 이상인 첫 번째 원소의 iterator를 반환한다.
- 해당하는 원소가 없다면 end()를 반환한다.
- 시간 복잡도는 O(log K)가 걸린다.
🔷 코드
#include <iostream>
#include <algorithm> // sort
#include <vector> // stl 정렬 쓰려고
#include <set> // multiset
using namespace std;
int N, K;
vector<pair<int, int>> gem; // 무게, 가격
multiset<int> bag;
long long ans;
int main()
{
// 보석 개수, 가방 개수
cin >> N >> K;
// 보석 info
for (int i = 0; i < N; i++)
{
int m, v;
cin >> m >> v;
gem.push_back({ m, v });
}
// 가방 info
for (int i = 0; i < K; i++)
{
int c;
cin >> c;
bag.insert(c); // 자동 정렬됨
}
// 보석 가격 내림차순 정렬
sort(gem.begin(), gem.end(), [](auto& a, auto& b)
{
if (a.second == b.second) return a.first < b.first;
return a.second > b.second;
});
// 가장 비싼 보석을 넣을 수 있는 최대한 딱 맞는 가방 찾기
for (int i = 0; i < N; i++)
{
int m = gem[i].first;
int v = gem[i].second;
// 이 보석을 담을 수 있는 가장 작은 가방 찾기
auto it = bag.lower_bound(m);
if (it != bag.end())
{
ans += v;
bag.erase(it); // 사용한 가방 제거
}
}
cout << ans;
return 0;
}
🔵 시도 3 우선순위 큐 사용
보석과 가방을 무게 기준 정렬한다.
그리고 가방을 순회하며 해당 가방에 담을 수 있는 모든 보석을 우선순위 큐에 넣고 가장 비싼 보석을 담는다.
이게 더 깔끔한 구현 같다!
🔷코드
#include <iostream>
#include <algorithm> // sort
#include <vector> // stl 정렬 쓰려고 원시 배열 대신 vector
#include <queue> // 우선 순위 큐
using namespace std;
int N, K;
vector<pair<int, int>> gem; // 무게, 가격
vector<int> bag;
long long ans;
int main()
{
// 보석 개수, 가방 개수
cin >> N >> K;
// 보석 info
for (int i = 0; i < N; i++)
{
int m, v;
cin >> m >> v;
gem.push_back({ m, v });
}
// 가방 info
for (int i = 0; i < K; i++)
{
int c;
cin >> c;
bag.push_back(c);
}
// 보석 무게 오름차순 정렬
sort(gem.begin(), gem.end());
// 가방 무게 오름차순 정렬
sort(bag.begin(), bag.end());
priority_queue<int> pq; // 가격 기준 max heap
int gem_i = 0; // 보석 인덱스
// 가방을 기준으로 어떤 보석을 담을지
for (int bag_i = 0; bag_i < K; bag_i++)
{
int bagWeight = bag[bag_i];
// 현재 가방에 담을 수 있는 보석들을 모두 pq에 넣음
// 자동 정렬 됨
while (gem_i < N && gem[gem_i].first <= bagWeight)
{
pq.push(gem[gem_i].second); // 가격만 넣음
gem_i++;
}
// 가장 비싼 보석을 선택
// 나머지 보석들은 아직 우선순위 큐에 저장되어 있다.
// 다음 가방에선 모두 포함하여 비교.
if (!pq.empty()) {
ans += pq.top();
pq.pop();
}
}
std::cout << ans;
return 0;
}
'PS' 카테고리의 다른 글
| [C++] Boj 14503 로봇 청소기 (1) | 2025.05.02 |
|---|---|
| [C++] Boj 10757 큰 수 A+B (0) | 2025.04.29 |
| [C++] Programmers Lv. 2 "짝지어 제거하기" (0) | 2025.04.29 |
| [C++] Programmers Lv. 2 "괄호 회전하기" (1) | 2025.04.25 |
| [C++] Programmers Lv. 2 "방문 길이" (0) | 2025.04.25 |