각각의 보석이 있을 때, 각 보석이 어떤 가방에 들어있는 지
각각의 가방이 있을 때, 가방에 보석이 들어있는 최적의 경우를 구한다.
가격이 큰 보석을 최대한 가져간다. 따라서 가격이 큰 순서대로 정렬하고, 자신보다 용량이 더 크지만 차이가 가장 적은 가방을 선택해 보석을 차례대로 넣는다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, k;
// int limits[100000000];
bool cmp(pair<int, int>& a, pair<int, int>& b) {
if (a.first == b.first) return a.second > b.second; // 가치 순대로 내림차순 정렬
else return a.first < b.first; // 가치가 같은 경우, 무게가 적은 것을 우선으로 둔다.
}
int main() {
vector<pair<int, int>> info(n); // 보석의 (무게, 가치)
vector<int> limit(k);
cin >> n >> k;
for (int i = 0; i < n; i++) {
int a, b; cin >> a >> b;
info.emplace_back(a, b);
}
for (int i = 0; i < k; i++) {
int l; cin >> l;
limit.push_back(l);
}
sort(info.begin(), info.end(), cmp);
int ret = 0;
vector<bool>visited(k, false);
// 용량에 가장 근접하되 작은 가방을 찾아 넣는다.
for (int i = 0; i < n; i++) {
int cand = 100000000, index = -1;
for(int bag = 0; bag < k; bag++){
if (limit[bag] >= info[i].first && visited[bag] == false) // 최대 용량이 이 보석보다 클 때,
if (cand > limit[bag]) {
cand = limit[bag];
index = bag;
}// 최대 용량이 가장 작은 가방을 찾는다.
}
if(index!= -1){
visited[index] = true;
ret += info[i].second;
}
}
cout << ret << endl;
return 0;
}
시간초과
해설
(1) 각각의 보석에 대해서 좋은 가방을 찾는 방법
난 이 방법을 고안했었다. 내가 놓친 부분은 여기서는 자료구조를 잘 선택해야했다. 이 문제에서 자료구조가 해야할 일은 (1) 어떤 수 X보다 크면서 가장 작은 값을 찾고 (이를 Lower Bound 라고 한다.) (2) 수를 지우는 작업을 해야한다. 해설에서는 BST (Binary Search Tree)를 이용했다.
[C++] multiset container 정리 및 사용법
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
using namespace std;
bool cmp(pair<int, int>& a, pair<int, int>& b) {
if (a.second == b.second) return a.first < b.first;
else return a.second > b.second;
}
int main() {
int n, k;
cin >> n >> k;
vector<pair<int, int>> info(n);
for (int i = 0; i < n; i++)
cin >> info[i].first >> info[i].second; // 무게, 가격
sort(info.begin(), info.end(), cmp);
multiset<int> capacity;
for (int i = 0; i < k; i++) {
int c; cin >> c;
capacity.insert(c);
}
long long ret = 0;
for (int i = 0; i < n; i++) {
auto iter = capacity.lower_bound(info[i].first); // 무게가 info[i].first보다 같거나 큰 것 중 첫번째 iterator를 반환한다.
if (iter != capacity.end()) { // 같거나 큰 무게를 찾지 못한 경우
ret += info[i].second;
capacity.erase(iter);
}
}
cout << ret << endl;
return 0;
}
이렇게 lower_bound를 사용해서 구현한다. 만약 현재 무게보다 큰 범위에서 찾아야 한다면 upper_bound를 사용하면 된다.
한 보석에 대해서 보석을 찾는 것에 LogK, 지우는 것에 LogK의 시간이 걸리므로 총 NLogK의 시간 복잡도가 걸린다.
(2) 각 가방에 대해서 적절한 보석을 찾는 방법
가방의 용량과 보석의 무게를 합쳐서 오름차순 정렬한다. 그리고 가방의 capacity 범위 안에 있는 보석들을 후보로 지정한다.
(1, 23), (2, 99), 2, (5, 65), 10