[BOJ] 1202 보석 도둑 (Python3)

문제

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.
상덕이가 털 보석점에는 보석이 총 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)

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

출력

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

예제 입력 1  
2 1
5 10
100 100
11
예제 출력 1  
10

예제 입력 2  
3 2
1 65
5 23
2 99
10
2
예제 출력 2 
164

문제풀이

이 문제는 우선순위 큐를 이용한 문제이다.

힙큐 리스트의 순서는 크기 순서가 아닌데 자꾸 리스트처럼 크기 순서라고 헷갈려서 푸는데 오래걸렸다. 힙큐는 힙트리를 리스트로 표현한것 뿐이고, heappop이나 heappush를 하면 알아서 가장 적은 값이 출력되고, 힙큐의 크기대로 push된다.

보석을 가장 적은 무게를 차지하는 보석의 순서중 가장 큰 가치를 갖는 보석부터 가방에 넣어야 한다. 가방의 무게들을 오름차순 정렬 한 뒤에, 하나씩 불러와 해당 무게보다 적은 무게를 갖는 보석을 모두 heappush 해준뒤 가장 가치가 큰값을 heappop해준다. 이때 최대힙으로 구성해야 하므로, push할때 -를 붙여 push해야 한다.

이런식으로 적은 무게에서 가장 큰 가치를 갖는 보석을 차례로 넣어주면, 가장 큰 총합의 가치의 보석을 도둑질 할 수 있다.

코드

import heapq

n,k = map(int, input().split())

jewels = []
for _ in range(n):
    jewels.append(list(map(int, input().split())))
jewels.sort()

bag = []
for _ in range(k):
    bag.append(int(input()))
bag.sort()

answer = 0

q = []

for b in bag:
    while jewels and b >= jewels[0][0]:
        heapq.heappush(q, -jewels[0][1])
        heapq.heappop(jewels)
    if q:  
        answer += heapq.heappop(q)
    elif not jewels:
        break

print(-answer)

2 1
5 10
100 100
11
10