[백준] 보석 도둑

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

1202번: 보석 도둑

 

이 문제의 알고리즘 분류가 정렬 또는 우선순위 큐가 있어서 heapq 와 sort() 로 오름차순으로 정렬하였다.

작은 가방에 들어갈 수 있는 보석은 큰 가방에 당연히 들어가기 때문이다. 오름차순으로 가방에 넣을 수 있는 보석의 가격을 price 에 놓고 heapq 와 '-' 부호를 이용하여 절댓값이 가장 큰 가격을 answer 에 더한다.   

 

import sys, heapq

N, K = map(int, sys.stdin.readline().split())
jewelry = []
bags = []
price = []
answer = 0

for i in range(N):
    heapq.heappush(jewelry, list(map(int, sys.stdin.readline().split())))

for i in range(K):
    bags.append(int(sys.stdin.readline()))

bags.sort()

for i in bags:
    while jewelry and i >= jewelry[0][0]:
        heapq.heappush(price, -1 * heapq.heappop(jewelry)[1])

    if price:
        answer -= heapq.heappop(price)
    else:
        if not jewelry:
            break

print(answer)