보석 도둑
Prob
보석 N개, 무게 M, 가격 V
가방 K개, 최대 무게 C, 최대 한 개 보석만 넣을 수 있음
보석의 최대 가격
Solv
가방과 보석을 C와 M을 기준으로 minheap 생성
가방은 C를 원소로 보석은 (M, V)를 원소로 함
C부터 하나씩 pop하면서 C보다 작은 M들을 V를 기준으로 maxheap에 담은 후 maxheap.top()으로 가능한 보석 중 가장 비싼 것 pop
남은 보석은 다음 C의 기준에 포함되므로 그대로 활용
Check
보석 [(1, 65), (5, 23), (3, 99), (6, 23), (2, 23)]
가방 [3,4,2,5,3]
| C | Vmax | sum |
|---|---|---|
| 2 | 65(1) 23(2) | 65 |
| 3 | 99(3) 23(2) | 99 |
| 3 | 23(2) | 23 |
| 4 | 0 | |
| 5 | 23(5) | 23 |
