티스토리 뷰
728x90
[Greedy] jewelryThief - priority_queue(heap)
예제: https://www.acmicpc.net/problem/1202
// 보석상 도둑 그리디 알고리즘
// 보석수, 가방수
// 한개의 가방에는 한개의 보석만 넣을 수 있다.
// 보석 무게, 보석 값어치
// 가방들마다 넣을 수 있는 무게
// algorithm > sort
// vector, queue
// pair, priority_queue(heap)
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define SIZE 300000
int main() {
int jewelryCount, bagCount;
cin >> jewelryCount >> bagCount;
// ---------------------------- //
vector<pair<int, int>> jewelry;
double weight, value;
for(int i=0; i<jewelryCount; i++) {
cin >> weight >> value;
jewelry.push_back({ weight, value });
}
// ---------------------------- //
int bagWeight[SIZE];
for(int i=0; i<bagCount; i++) {
cin >> bagWeight[i];
}
sort(bagWeight, bagWeight+bagCount);
sort(jewelry.begin(), jewelry.end());
// ---------------------------- //
priority_queue<int> heap;
long long maxValue = 0;
for(int i=0, j=0; i<bagCount; i++) {
// 가방에 넣을 수 있는 보석들을 모두 힙에 넣는다.
while(j < jewelryCount && jewelry[j].first <= bagWeight[i]) {
heap.push(jewelry[j].second);
j++;
}
// 힙에 넣은 것들중 크기가 제일 큰 것을 지금 가방에 넣는다.
if(heap.size()) {
maxValue += heap.top();
heap.pop();
}
}
cout << maxValue << endl;
return 0;
}
728x90
'공부' 카테고리의 다른 글
[Sort] QuickSort (0) | 2018.09.11 |
---|---|
[DP] changeCoin? (0) | 2018.09.08 |
[Greedy] jewelryThief - priority_queue(heap) (0) | 2018.09.08 |
[SQL] groupBy & having? (0) | 2018.09.08 |
[SQL] join? (0) | 2018.09.08 |
[SQL] where & orderBy & limit (0) | 2018.09.08 |
댓글