[Python] 백준 1202 보석 도둑

 

문제

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

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

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

 

 

 

 

난이도

골드2

 

 

 

 

내 코드

import sys
import queue

n, k = map(int,sys.stdin.readline().split())
gem = []
bag = []
answer = 0
priority_queue = queue.PriorityQueue() 
for _ in range(n) :
    m, v = map(int,sys.stdin.readline().split())
    gem.append((m,v)) # 무게, 가격
for _ in range(k) :
    c = int(sys.stdin.readline())
    bag.append(c)

bag.sort()
gem.sort() # 보석 무게가 가벼운 순으로 정렬
i = 0

for b in bag :
    while i < n :
        if gem[i][0] <= b :
            priority_queue.put(-gem[i][1])
        else :
            break
        i += 1
    
    if not priority_queue.empty() :
        answer += priority_queue.get()

print(-answer)

 

 

 

풀이과정

처음에는 그냥 보석 리스트를 보석의 가격 > 가벼운 순 으로 sort 한 뒤에 가방은 가벼운것부터 하나하나 비교해가며 답을 찾았더니 당연하게도 시간초과가 떴다.

우선순위 큐를 사용하여 가방은 일단 가벼운 순으로 정렬해두고, 가방을 하나씩 돌아가면서 현재 가방에 넣을 수 있는 무게와 보석의 무게를 비교해가며 넣을 수 있는 보석은 큐에 넣고(뒤에는 더 무거운 가방들만 있기 때문에 한 번 큐에 들어간건 뺄 일이 없음), 그 중 가격이 가장 비싼 하나를 get하여 답을 구했다. PriorityQueue 는 최소힙으로 작동하기 때문에 최댓값을 찾으려면 -를 사용하여 넣고 빼면된다.

우선순위 큐만 알고있다면 쉬운 문제.