[알고리즘][python] 백준 1202

문제 정의

입력 : 첫째줄 N(보석 개수), K(가방 개수)
다음 N개 줄에 각각 보석의 무게와 가격 입력
다음 K개 줄에 가방에 최대 담을 수 있는 무게 입력
출력 : 하나의 가방에 하나의 보석밖에 안들어갈 때, 가지고 있는 가방으로 최대의 가격을 뽑아내라.

ex)
3 2
1 65
5 23
2 99
10
2

문제 풀이

무조건 가격을 우선순위로 봐야한다. 어떤 가방 X가 C까지의 무게까지 버틴다고 했을 때, 1~C의 무게를 가지고 있는 보석들 중 하나가 가방 X에 들어갈 수 있다. 이 때, 이 보석들 중 가장 비싼거를 선택하고 나머지는 쳐낸다.
위의 알고리즘을 C가 가장 작은 가방부터 시작해서 C가 가장 큰 가방까지 진행한다.
중요한 점은 가방에 들어간 보석은 다음 계산부터 안봐도 된다는 점이다.
이를 위해 파이썬에서 지원하는 PriorityQueue를 사용했다.

파이썬의 PriorityQueue

1. 선언은 from queue import PriorityQueue 으로 한다.
2. 변수를 만든다. myQue = PriorityQueue()
3. 값을 넣는다.

myQue.put(3)
myQue.put(1)
myQue.put(5)

4. 값을 뱉는다. myQue.get()

이 때, myQue.get()은 어떤 값을 뱉을까?
print(myQue.get())을 해보면 1을 뱉는다. 왜냐하면, 넣은 값인 1,3,5중 1이 가장 작기 때문이다.

PriorityQueue는 우선순위 큐라고 부른다. 그냥 큐(Queue)는 먼저 넣은 애가 나온다. 하지만 우선순위 큐는 말그대로 우선순위가 있다. 가장 작은 값이 나오니까.

파이썬 내장 우선순위 큐는 가장 작은 값을 뱉는다. 그렇다면 가장 높은 값을 뱉으려면 어떻게 해야할까? 넣을 때 -를 붙여서 넣으면 된다.

내 코드

import sys
from queue import PriorityQueue

N, K = map(int, sys.stdin.readline().split())
sum = 0
boseok = []
myQue = PriorityQueue()
bag = []

for i in range(N):
    boseok.append(list(map(int, sys.stdin.readline().split())))

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

bag.sort()
boseok.sort(key = lambda x : x[0])

bsIdx=0
for i in range(K):
    while bsIdx<N and bag[i] >= boseok[bsIdx][0]:
        myQue.put(boseok[bsIdx][1]*(-1))
        bsIdx += 1
    if not myQue.empty():
        sum += myQue.get()

print(-sum)