티스토리 뷰

알고리즘

[Greedy] jewelryThief - priority_queue(heap)

seunggabi 승가비 2018. 9. 8. 22:54

[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;
}


'알고리즘' 카테고리의 다른 글

[Sort] QuickSort  (0) 2018.09.11
[DP] changeCoin?  (0) 2018.09.08
[Greedy] jewelryThief - priority_queue(heap)  (0) 2018.09.08
[Math] changeProposition?  (0) 2018.09.08
[Graph] Floyd Warshall?  (0) 2018.09.08
[Sort] 수열에서 자기 위치에 위치하는 원소가 있는지 확인?  (0) 2018.09.07
댓글
댓글쓰기 폼