<정렬> 1202번 보석 도둑 with 파이썬

 

문제

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

 

상덕이가 털 보석점에는 보석이 총 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)

 

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

출력

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

정답비율

22.243%

알고리즘 분류

 #자료구조 #그리디 #정렬 #우선순위큐

 

import sys
import heapq
input = sys.stdin.readline
# 보석 n개, 가방 k개, 무게 m, 가격 v, 최대무게 c
n, k = map(int, input().split())
pq = []
lst = []
bags = []
for _ in range(n):
    m, v = map(int, input().split())
    lst.append((m, v))
for _ in range(k):
    bags.append(int(input()))
bags.sort() # 오름차순으로 정렬
lst.sort(reverse=True) # 내림차순으로 정렬
answer = [0] * k
for i in range(k):
    while lst:
        if lst[-1][0] > bags[i]:
            break
        m, v = lst.pop()
        heapq.heappush(pq, (-v, m)) # 가격이 클 수록 먼저 pop
    if pq:
        v, m = heapq.heappop(pq)
        answer[i] = -v
print(sum(answer))

 

 - 가방은 오름차순으로 정렬하여 작은 가방부터 확인하도록 하였다.

 

 - 보석은 내림차순으로 정렬하고 오른쪽 부터 pop하며 우선순위큐에 넣었다. 우선순위큐에 넣을 때는 가방의 제한무게를 확인한 후 괜찮을 경우 가격에 대한 최대힙이 되도록 하였다.

 

 - 우선순위 큐의 가장 앞에는 현재 가방에 들어갈 수 있는 최대값의 보석이 있으므로 가방에 넣으면 끝이다. 

 

 - 시간복잡도는 (N + K) * logN 일 것이다. (아마도...)

 

---

 

 

참고

 

1202번: 보석 도둑