백준 1202. 보석 도둑

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

1202번: 보석 도둑

 

방법을 알면 정말 쉽고 모르면 정말 모르겠는 그리디 & 우선순위큐 문제 .. 

방법을 알면 정말 단순하다.

 

보석은 {무게, 가격} 으로 저장해 무게 기준 오름차순 정렬한다.

가방도 무게기준 오름차순 정렬한다.

 

이런 문제는 어떤걸 기준으로 탐색하는지가 정말 중요한데 여기서는 가방을 기준으로 탐색을 한다.

 

1. 현재 가방에 넣을수 있는 보석들을 모두 우선순위큐 (max heap) 에 넣는다. 

2. 우선순위큐가 기본 max heap이므로 top에 가장 가격이 높은 보석이 있을 것이다. 

3. 해당 보석을 선택하고 pop 한다. 

 

위를 모든 가방에 대하여 수행한다. 

물론 우선순위큐가 비었을때 같은 경우도 처리해줘야 한다. (보석보다 가방이 많을때 같은 경우)