[백준] [C++] 1202번 보석 도둑 (greedy, priority queue)
2021. 6. 30. 08:46ㆍ알고리즘/백준
1. 문제
2. 풀이
이 문제는 탐욕법으로 해결할 수 있다.
가장 값비싼 보석을 가능한 가방중 가장 용량이 작은것에 넣는 것이다.
하지만 배열을 사용하여 문제를 풀 시 시간초과가 나온다.
따라서 적절히 사용한 가방을 제외 하고, 빠르게 작은 가방을 찾을 수 있는 자료구조를 사용해야한다.
map을 사용하면 빠르게 원소를 제외할 수 있고, 최소 원소 또한 찾을 수 있다.
전체적인 알고리즘은 다음과 같다
1) 보석을 가중치 V에 대하여 정렬
2) 가방을 map에 담아 자동적으로 정렬, 중복된 개수를 value로
3) 가중치가 제일 높은것을 담을 수 있는 가방중 가장 작은 용량에 담는다.
4) 가방에 넣으면 그 가방은 고려대상에서 제외한다.
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 <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
int N, K;
map<int, int> C;
vector<pair<int, int> > item;
long long answer = 0;
void solve(int iidx) {
if(iidx == -1) {
return;
}
auto lo = C.lower_bound(item[iidx].second);
for(auto it = lo; it != C.end(); it++) {
if(it->second > 0) {
answer += item[iidx].first;
it->second--;
if(it->second == 0) {
C.erase(it->first);
}
break;
}
}
return solve(iidx-1);
}
int main() {
cin>> N >> K;
item = vector<pair<int, int> >(N);
for(int i = 0; i < N; i++) {
cin>>item[i].second>>item[i].first;
}
sort(item.begin(), item.end());
for(int i = 0; i < K; i++){
int tmp;
cin>>tmp;
C[tmp]++;
}
solve(N-1);
cout<<answer;
}
|
cs |
3. 다른사람 풀이 - priority queue
'알고리즘 > 백준' 카테고리의 다른 글
[백준] [C++] 2473번 세 용액 (bsearch, two pointer) (0) | 2021.07.01 |
---|---|
[백준] [C++] 1208번 부분수열의 합2 (조합, 중간에서 만나기) (0) | 2021.06.30 |
[백준] [C++]12852번 1로 만들기 (dp, tracking) (0) | 2021.06.29 |
[백준] [C++] 2261번 가장 가까운 두 점 (sweeping) (0) | 2021.06.29 |
[백준] [C++] 11444번 피보니치 수 6 (분할정복) (0) | 2021.06.29 |