[골드 2] 백준 1202 - 보석 도둑 (파이썬)

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

풀이

정렬 + 그리디 + 우선순위 큐 알고리즘으로 해결 할 수 있다.

문제의 핵심은 무게 제한이 있는 가방에 최대 가치를 가지는 보석을 훔치는 방법이다.

J = [tuple(map(int, input().split())) for _ in range(N)]
B = [int(input()) for _ in range(K)]
 
J.sort()
B.sort()

• 보석 리스트 J는 무게 기준 오름차순 정렬
• 가방 리스트 B는 무게 제한 기준 오름차순 정렬

가방을 무게 제한이 작은 순서대로 처리하면서, 해당 가방에 담을 수 있는 보석 중 가장 비싼 보석을 선택한다.

pq = PriorityQueue()
answer = 0
pos = 0

• 최대 힙을 구현하기 위해 - 가격을 우선순위 큐에 집어 넣는다.
• pos는 보석 리스트에서 현재 가방까지 확인한 보석의 인덱스를 저장한다.

for i in range(K):
    while pos < N and J[pos][0] <= B[i]:
        pq.put(-J[pos][1])
        pos += 1

• 현재 가방 B[i]에 담을 수 있는 보석을 모두 우선순위 큐에 삽입한다.
• 우선순위 큐는 가격이 높은 순으로 정렬된 힙 역할을 한다.

if pq.qsize() > 0 :
  answer += -pq.get()

• 가장 가치 높은 보석을 꺼내어 담는다.

코드

# 백준 1202 - 보석 도둑
# 분류 : 정렬
 
import sys
from queue import PriorityQueue
 
input = sys.stdin.readline
 
N, K = map(int, input().split())
 
J = [tuple(map(int, input().split())) for _ in range(N)]
B = [int(input()) for _ in range(K)]
 
J.sort()
B.sort()
 
pq = PriorityQueue()
 
answer = 0
pos = 0
for i in range(K) :
    while pos < N and J[pos][0] <= B[i] :
        pq.put(-J[pos][1])
        pos += 1
    
    if pq.qsize() > 0 :
        answer += -pq.get()
 
print(answer)