13. 백준 1202 (골드2) : 보석 도둑 _ python풀이

문제

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

상덕이가 털 보석점에는 보석이 총 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)

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

출력

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

예제 입력 1 복사

2 1
5 10
100 100
11

예제 출력 1 복사

10

예제 입력 2 복사

3 2
1 65
5 23
2 99
10
2

예제 출력 2 복사

164

---

*문제해석

이 문제는 '그리디 알고리즘' 문제다. 

각 가방별로 훔칠 수 있는 보석을 탐색해야하기 때문에 보석의 무게별로, 가격, 가방이 감당 가능한 최대무게 리스트 들을 오름차순으로 정렬하는게 효과적이다. 그렇기 때문에 '최대힙'자료구조를 사용하는것이 좋을 것이다.

파이썬에서 지원하는 heapq는 최소힙이다. 여기에 들어가는 수를 음수로 만든다면 자연스레 절댓값만 비교했을 때 최대힙 자료구조가 될 것이다.

 

 

*나의코드

import sys
import heapq
input=sys.stdin.readline

n,k = map(int,input().split())

jewel = [[*map(int,input().split())] for _ in range(n)]
bag = [int(input()) for _ in range(k)]

jewel.sort()
bag.sort()
result=0
tmp = [] #최소힙 / 보석의 가격저장 리스트

for i in bag: #가방무게에 대해
    while jewel and jewel[0][0] <= i: #제일 가벼운 보석무게를 가방이 허용하는가?
        heapq.heappush(tmp, -jewel[0][1]) #그렇다면 가격을 저장한다 ('-'를 붙여 최소힙을 최대힙으로 사용한다)
        heapq.heappop(jewel)
    if tmp:
        result -= heapq.heappop(tmp) #제일 가치높은 것을 추출 (음수이기 때문에 -= 을 해준다)
print(result)

 

*중요한점

1. 최소힙 자료구조를 음수로 저장하였을 때 최대힙 자료구조로 이용할 수 있다.

2. 이는 제일 가치가 높은 것을 추출할 때 사용된다.