[Baekjoon] 보석 도둑 / Python, 파이썬 / 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)

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

출력

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

예제 입력 1

2 1
5 10
100 100
11

예제 출력 1

10

예제 입력 2

3 2
1 65
5 23
2 99
10
2

예제 출력 2

164

문제 풀이

import sys
import heapq

input = sys.stdin.readline

N, K = map(int, input().split())
gems = []
bags = []

for _ in range(N):
    M, V = map(int, input().split())
    gems.append((M, V))

for _ in range(K):
    bags.append(int(input()))

gems.sort()
bags.sort()

heap = []
cur = 0
result = 0

for bag in bags:
    while cur < N:
        M, V = gems[cur]
        if bag >= M:
            heapq.heappush(heap, -V)
            cur += 1
        else:
            break
    
    if len(heap) > 0:
        V = -heapq.heappop(heap)
        result += V

print(result)