[백준 알고리즘] 1715번: 카드 정렬하기
March 11, 2021
https://www.acmicpc.net/problem/1715
문제
문제
첫째 줄에 테스트 케이스의 수가 주어진다.
각 케이스의 첫 줄에 정수 N(1 ≤ N ≤ 1,000)과 M(1 ≤ M ≤ 1,000)이 주어진다. 다음 줄부터 M개의 줄에는 각각 정수 ai, bi가 주어진다. (1 ≤ ai ≤ bi ≤ N)
입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.
출력
각 테스트 케이스마다 백준이가 책을 줄 수 있는 최대 학생 수를 한 줄에 하나씩 출력한다.
풀이
코드
' '
#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);
}
