[백준] 1202번 | 보석 도둑

풀기 전 생각 정리

1) 1 <= 보석 개수, 가방 개수 <= 300,000이므로 복잡도에 유의
2) 작은 순으로 가방을 선택해, 담을 수 있는 보석 중 가장 비싼 가격을 가진 보석을 선택해서 꺼낸다.
3) 2번을 구현하기 위해 첫번째 for문을 for b in bag 으로 설정하고, 안에서 보석을 순회하면서 선택하려 했다.
4) 3번을 구현하기 위해 heapq를 사용하려 했다.
5) 러프하게 수도코드를 짤 때는 보석을 순회하는 부분을 어떻게 해결해야 할지 고민이 많았다.

코드

import sys
import heapq

n, k = map(int, sys.stdin.readline().split())
jewelry = []
bag = []

for i in range(n): // 작은 무게 순으로 보석을 접근하기 위함
    weight, price = map(int, sys.stdin.readline().split())
    heapq.heappush(jewelry, (weight, price))

for i in range(k): // 담을 수 있는 무게가 작은 가방부터 접근하려고
    heapq.heappush(bag, int(sys.stdin.readline()))

result = 0
tmp_bag = []
for _ in range(k): // 가방의 개수만큼 반복
    bag_w = heapq.heappop(bag)

	//현재 선택된 가방에 담을 수 있는 보석들을 tmp_bag에 저장
    while jewelry and bag_w >= jewelry[0][0]: 
        heapq.heappush(tmp_bag, -heapq.heappop(jewelry)[1])

	//현재 가방에 담을 수 있는 보석 중 가격이 제일 높은 것을 담기
    if tmp_bag: 
        result -= heapq.heappop(tmp_bag)

	// 담을 보석이 없는 경우 가방의 존재 유무에 상관없이 종료
    elif not jewelry and tmp_bag:
        break

print(result)

풀이

가방을 작은 무게부터 접근해서, 해당 가방에 담을 수 있는 보석들을 빼내 가치가 높은 보석 하나만을 취한다.
보석, 가방 모두 무게에 따른 최소힙을 사용한다. 가치가 높은 보석을 취할 땐 최대힙을 사용한다.
복잡도 문제는 N+K로 해결할 수 있었다.