[백준 알고리즘] 1202번: 보석도둑
March 11, 2021
https://www.acmicpc.net/problem/1202
문제
문제
세계적인 도둑 상덕이는 보석점을 털기로 결심했다.
상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.
상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)
다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)
다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)
모든 숫자는 양의 정수이다.
출력
첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.
풀이
처음엔 냅색 문제인 줄 알았는데, 가방에 한번에 하나만 넣어야 한다는 조건이 있었다. 따라서 최적의 답을 찾으려면 가장 크기가 작은 가방에 들어갈 수 있는 보석 중 가치가 가장 큰 보석을 넣어주어야 한다.
가방의 들어갈 수 있는 보석은 무게가 최소한 보석의 무게가 된다는 점을 이용하면 모든 가방에 보석을 다 넣어보지 않아도 쉽게 들어갈 보석을 골라낼 수 있다. 우리는 set 컨테이너에 들어있는 lower_bound 를 이용할 것이다.
lowerbound 함수는 set에서 인자로 주어진 어떤 값이 찾는데, 만약 그 값이 존재하지 않는다면, 해당 값 보다 큰 값 중 가장 작은 값을 선택해서 그 iterator를 반환한다. set 에 가방들을 모두 넣어두고, lowerbound의 인자로 가장 가치가 큰 보석부터 찾아보면 해당 보석을 담을 수 있는 배낭의 iterator 를 얻게 된다.
배낭에 보석을 넣게 되면 더 이상 보석을 넣을 수 없기 때문에, set에서 배낭을 삭제하고 모든 배낭에 보석을 넣을 때까지 위 작업을 반복한다. multiset을 이용한 이유는 일반 set 컨테이너는 중복된 key를 허용하지 않기 때문에 최대 무게가 같은 배낭이 여러개 있을 경우를 처리하지 못하기 때문이다.
코드
' '
#include <cstdio>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<int, int>> jewels;
multiset<int> bags;
bool comp (pair<int, int> a, pair<int, int> b){
if (a.second == b.second){
return a.first < b.first;
}
return a.second > b.second;
}
int main (){
int N, K;
scanf("%d %d", &N, &K);
for (int i = 0 ; i < N ; i ++){
int weight;
int value;
scanf("%d %d", &weight, &value);
jewels.push_back({weight, value});
}
sort(jewels.begin(), jewels.end(), comp);
for (int i = 0 ; i < K ; i++){
int bag;
scanf("%d", &bag);
bags.insert(bag);
}
long long sum = 0;
for (auto jewel : jewels){
if (bags.empty()) break;
auto iter = bags.lower_bound(jewel.first); // 현재 보석의 무게 이상의 첫번째 가방을 찾는다.
if(iter != bags.end()){
sum += jewel.second; // 보석의 가치를 더하고
bags.erase(iter); // 해당 가방은 찾을 대상에서 제외시킨다.
}
}
printf("%lld", sum);
}
