[알고리즘] 보석도둑 백준 1202 python

문제 바로가기

---

풀이

가장 작은 용량의 가방에 넣을 수 있는 가장 비싼 보석을 넣어야 한다.
따라서 기준을 가방의 용량(오름차순)으로 잡고 시작한다.

1. 가방의 용량을 오름차순으로 정렬하고 거기에 들어갈 수 있는 보석들을 전부 고른 후 가장 비싼 보석을 가방에 담는다.
2. 골라진 보석들은 가장 용량이 적은 가방에 들어갈 수 있는 보석들이므로 다른 가방에도 들어갈 수 있다.
3. 따라서 1번을 반복하며 가방에 넣을 수 있는 보석들을 전부 고른 후 그 중 가장 비싼 보석을 가방에 담으면 된다.

이 문제를 풀기 위해서는 우선순위 큐에 대해서 알아야한다.

큐(Queue)

FIFO구조
먼저 들어온 데이터가 먼저 나가는 구조

힙(Heap)

힙은 완전 이진트리
최대 힙(Max Heap): 완전 이진트리이면서 자식노드보다 부모노드에 저장된 값이 더 커지는 구조.
최소 힙(Min Heap): 완전 이진트리이면서 자식노드보다 부모노드에 저장된 값이 더 작아지는 구조.

우선순위는 항상 부모노드가 더 높은 것이 와야하고, 최대 힙과 최소 힙을 나누는 기준은 우선순위가 값이 작은 순서대로이냐, 큰 순서대로이냐에 따라 나뉜다.

파이썬에서는 기본적으로 최소 힙으로 구현되어있다.

우선순위 큐(Priority Queue)

들어간 순서에 상관 없이 우선 순위가 높은 데이터가 먼저 나오는 큐
일반적으로 힙(Heap)을 이용해서 구현할 수 있음.
다른 자료구조가 아닌 힙을 이용해서 구현하는 이유는 배열이나 링크드리스트보다 빠르게 삽입니다 반환을 할 수 있다.

import sys
import heapq

N, K = map(int, input().split())
result = 0

jems = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
bags = []
for _ in range(K):
  bags.append(int(sys.stdin.readline()))


jems.sort()
bags.sort()

heap = []

for bag in bags:
    while jems and bag >= jems[0][0]: 
        heapq.heappush(heap, -heapq.heappop(jems)[1]) 
    if heap:
        result += heapq.heappop(heap)
    elif not jems:
        break

result = -result
print(result)