1202 Jewelry thief
알고리즘
1
2
3
4
5
6
7
8
9
10
1. 보석을 가치순으로 내림차순으로 정렬
2. 가방을 multiset에 저장함
3. 가치가 큰 보석부터 차례대로 꺼내면서 적절한 가방을 선택하고, 집어넣음
-적절한 가방 : 무게가 같으면 가장 적절. 같지 않으면 남는 무게가 가장 적은 가방
-찾는 법
1. 같은 게 있는지 확인
2. 없으면, 현재 검사하는 보석의 무게를 넣고 그대로 빼면 넣었던 자리에 있는 옆 가방의 반복자가 반환되는데
이 반복자가 multiset.end()와 같으면 보석 무게가 너무 무거워서 넣을 수 있는 가방이 없는 것이므로 다음보석 검사
아니면 그 반복자가 가리키는 가방에 집어넣는다.
-집어넣은 다음엔 multiset에서 넣은 가방을 삭제한다.
푼 과정
1
2
3
4
5
6
7
8
9
10
11
12
1. 보석은 가치순으로 정렬하고, 무게가 가장 적절한 가방에 넣어야된다고 생각함
2. 가치순으로 정렬하는 거야 쉬운데 적절한 가방을 택하는 과정이 어려웠음
-N*N 방법 : 순차탐색. 가방무게 - 보석무게 의 결과가 0또는 양수인 것중 첫번째를 적절한 가방으로 선택. 끝까지가면 없는 것
-> 당연히 시간초과남
-NlogN방법 : 이분탐색. 적절한 가방무게를 이분탐색함.
-> 가방을 하나씩 찾을 때마다, 빈 가방이 생기는데, 이 빈가방이 많아질수록 탐색의 시간이 더 걸리게 됨.(빈가방을 피하는 시간이 계속 증가함)
-> 그리고 보석과 같은 무게를 찾는게 아니다보니 제대로 찾는 것 같지도 않음
3. 이분탐색식으로 하되, 가방을 선택할 때마다, 그 자료구조에서 가방을 지우되 가방을 지우는 연산이 복잡하지 않은 자료구조를 선택해야겠다는 생각이 듦
-> 이진탐색트리로 해야겠다고 생각이 듦
4. 하지만 솔직히 이진탐색트리를 구현해본적이 한번도 없음
5. 고민하던 중 set과 multiset에 대해 알게됨
6. set인 중복이 없는 이진탐색트리처럼, multiset은 중복이 잇는 이진탐색트리처럼 사용할 수 있다는 것을 알게 됨
과제
1
1. 이진탐색트리 구현 방법을 공부해보자.
코드
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <algorithm>
#include <set>
#define MAX 3000000
using namespace std;
typedef struct Jewelry {
int weight;
int value;
bool operator < (Jewelry j) {
if (value != j.value)
return value > j.value;
else
return weight < j.weight;
}
} Jewelry;
Jewelry jewelry[MAX];
multiset<int> bag;
int numOfJewelry, numOfBag;
long long maxValue();
int main() {
cin >> numOfJewelry >> numOfBag;
for (int i = 0; i < numOfJewelry; i++)
cin >> jewelry[i].weight >> jewelry[i].value;
for (int i = 0; i < numOfBag; i++) {
int temp;
cin >> temp;
bag.insert(temp);
}
cout << maxValue();
}
//무게 넣어서 현재 위치 찾고, 현재 위치의 다음번 가방에 집어넣는 식
long long maxValue() {
sort(jewelry, &jewelry[numOfJewelry]);
long long value = 0;
for (int i = 0; i < numOfJewelry; i++) {
if (bag.empty())
break;
multiset<int>::iterator find = bag.find(jewelry[i].weight);
if (find == bag.end()) {
multiset<int>::iterator index = bag.insert(jewelry[i].weight);
multiset<int>::iterator temp = bag.erase(index);
if (temp == bag.end())
continue;
else
bag.erase(temp);
}
else
bag.erase(find);
value += jewelry[i].value;
}
return value;
}