[백준 01202] 보석 도둑 [Python]

문제

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

 

1202번: 보석 도둑

---

풀이

K개의 가방 용량 C(i)를 넘지않는 K개의 가장 비싼 보석을 선택하는 Greedy 문제다.

N, K모두 300,000이하이므로 K개의 가방에 대해 N개의 보석을 선택해 채워넣는 방법을 모두 계산하면 시간초과가 발생한다.

따라서, 보석을 Priority Queue에 저장해 탐색 시간을 줄여주는 방식으로 풀이했다.

 

우선 입력받은 보석과 가방을 용량순으로 정렬하자.

동일 무게의 보석에 대한 가격의 순서는 상관없다.

 

이제 가방의 용량을 초과하지 않는 보석들을 선형 탐색하며 최대 힙(expensive_gems)에 보석의 가격을 저장해주자.

 이미 탐색한 보석은 최대힙에 저장되므로 idx를 증가시켜 중복 탐색을 막아주자.

 

만약 최대힙에 저장된 보석이 있다면, 가장 가격이 비싼 보석 1개를 담으면 된다.

---

소스코드

보기