Life Engineering
[BOJ 1202] 보석 도둑(C++) 본문
https://www.acmicpc.net/problem/1202
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
#include <bits/stdc++.h>
using namespace std;
struct compare{
bool operator()(pair<long long,long long> a, pair<long long,long long> b){ //가격별 내림차순
return a.second < b.second;
}
};
bool comp(pair<long long,long long> a, pair<long long,long long> b){ //무게순 정렬(오름차순)
return a.first < b.first;
}
int main(){
long long N,K;
long long M,V,C;
long long ans=0;
cin>>N>>K;
vector<pair<long long, long long> > jewels;
vector<long long> bags;
priority_queue<pair<long long,long long>, vector<pair<long long,long long> >, compare> pq;
for (long long i=0; i<N; i++){
cin>>M>>V;
jewels.push_back(make_pair(M,V));
}
for (long long i=0; i<K; i++){
cin>>C;
bags.push_back(C);
}
sort(bags.begin(), bags.end());
sort(jewels.begin(), jewels.end(), comp);
long long count=0;
for (long long i=0; i<K; i++){
while(true){
if (count>=N || jewels[count].first>bags[i]){ //무게 넘치면
break;
}
pq.push(jewels[count]);
count++;
}
if (!pq.empty()){
ans+=pq.top().second;
pq.pop();
}
}
cout<<ans<<endl;
}
|
cs |
우선순위 큐를 이용하는 문제.
일단 보석을 무게 오름차순으로 정렬한다.
가방도 무게 오름차순으로 정렬한다.
priority queue 를 만들어서, 가방을 하나씩 선택할때마다 가방에 들어갈 수 있는 모든 보석을 큐에 집어넣는다.
큐의 compare 함수는 무게순으로 지정해놓았다. 즉 무게가 무거울수록 큐의 맨 앞에 위치하게 되고 따라서 가능한 최대의 이득을 얻을 수 있다.
아까 선택한 i번째 가방이 곧 선택할 i+1번째 가방보다 가벼우므로, 큐에 남은 애들을 i+1가 당연히 넣을 수 있다.
1) 우선순위 큐를 사용해서 최대의 이득을 취하기
2) 가방, 쥬얼리를 오름차순 정렬하기
'Problem Solving' 카테고리의 다른 글
[BOJ 1261] 알고스팟 (C++) (0) | 2021.08.09 |
---|---|
[BOJ 9202] Boggle (C++) (0) | 2021.07.22 |
[BOJ 1927] 최소 힙(C++) (0) | 2021.07.22 |
[BOJ 3055] 탈출 (C++) (0) | 2021.07.20 |
[프로그래머스] 숫자 문자열과 영단어(2021 카카오 인턴십 기출) (0) | 2021.07.15 |