백준 1202번: 보석 도둑

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

1202번: 보석 도둑

문제

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

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

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

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

 

 

---

 

import sys,heapq
input=sys.stdin.readline

n,k=map(int,input().split()) #보석n개, 가방k개

jewel=[]
for i in range(n):
    Mi,Vi=map(int,input().split()) #보석의 무게M,가격V
    heapq.heappush(jewel,[Vi,Mi])
bag=[]
for i in range(k):
    Ci=int(input()) #가방에 담을 수있는 최대무게
    heapq.heappush(bag,Ci)


result=0
capable_gem=[] #현재 가방의 용량보다 가벼운 보석

for i in range(k): #가방을 하나 선택
    Ci=heapq.heappop(bag) #가장 가벼운 가방 pop

    while jewel and Ci >= jewel[0][0]: #현재 가방의 용량보다 가벼운 보석에 관해
        weight,value = heapq.heappop(jewel) #최소 무게부터 하나씩 heappop
        heapq.heappush(capable_gem,-value) #보석의 가치만 최대힙으로 heappush

    if capable_gem:
        result+=(-heapq.heappop(capable_gem))
    elif not jewel: #capable_gem도 없고 jewel도 없을때. (보석이 아무것도없음)
        break

print(result)

작은가방부터 하나씩 선택해서, 선택한 가방보다 가벼운 보석은 모두 capable_gem 리스트에 넣어둔다

한 가방에 capable_gem에 든 비싼 보석부터 하나씩 넣는다

 

작은가방부터 하나씩 선택하기 때문에..  capable_gem에 넣은 보석은 다음 가방에도 넣을 수 있는 크기구나