우선순위 큐. [1202]

[1. 문제 설명]

https://www.acmicpc.net/problem/1202

---

[2. 풀이 접근]

카테고리는 우선순위 큐를 이용해서 푸는 방법이지만,

map 을 이용해서 풀 수 도 있다.

---

map 을 이용한 풀이

기본적인 전략은 아래와 같다.

• 훔친 보석의 가격을 최대로 해야 하므로,
• 보석 가격 순을 내림차순 정렬 후, 하나 씩 가져가는 방식이다.
• 이 때, 보석 무게가 도둑이 갖고 있는 가방 들 중 어느 하나에 포함될 수 있어야 한다.
• 이 때 이분 탐색을 위해, 가방 무게 역시 오름차순으로 미리 정렬 되어 있어야 한다.

그래서 보석을 기준으로 iterate 하면서 보석을 선택적으로 취해 나가는 것이다.

단) 여기서 아래와 같은 문제가 있다.

• 이번 보석을 어느 가방에 넣었으면, 이 가방은 다음 탐색에서 제외 되어야 한다.
• 그런데, 이분 탐색하는 배열을 대상으로 특정 원소를 제거 하려면, O(KlogK) 시간 복잡도가 발생한다.
• 바깥 for 문 까지 고려하면, O(NKlogK) 이므로 시간 초과가 발생할 것이다.  

그래서 배열을 대상으로 이분 탐색을 진행하지 않고,

std::map 을 대상으로 이분 탐색을 진행한다.

• 별도 compare 를 지정하지 않으면, key 를 대상으로 오름 차순으로 정렬된다.
• node 에 대한 insert 와 erase 를 O(logN) 에 할 수 있다.

마지막으로 주의 할 점은 동일한 무게를 갖는 가방이 여러 개 일 수 있다는 점이다.

그래서 map 에서 가방을 제거할 때, 해당 가방의 개수를 따로 counting 할 필요가 있다.

---

우선 순위 큐를 이용한 풀이

map 을 이용한 풀이와 조금 다르다.

여기서는 가방을 기준으로 iterate 한다.

• 먼저, 보석과 가방 모두 무게를 기준으로 오름차순 정렬을 한다.
• 가방을 기준으로 바깥 for 문을 만든다.
• for 문 안쪽에서는 현재 가방에 넣을 수 있는 모든 보석의 가격을 MaxHeap 에 푸쉬한다.
• 다음 보석을 이번 가방에 넣을 수 없는 경우,
• 현재 MaxHeap 의 top 에 오는 보석의 가격을 전체 결과에 더해준다.

이 방법에서는 map 을 이용한 풀이에서 고민했던 문제를 해결 할 수 있다.

현재 가방에 담을 수 있는 보석을 선택하는 것이기 때문이다.

---

[3. 코드 - map 을 이용한]

---

[3. 코드 - 우선순위 큐를 이용한]