[BaekJoon] 보석 도둑 - 1202 (Gold II, Python3)

 

문제 링크

1202번: 보석 도둑

성능 요약

메모리: 106592 KB, 시간: 2180 ms

분류

자료 구조, 그리디 알고리즘, 우선순위 큐, 정렬

제출 일자

2024년 3월 28일 17:51:01

문제 설명

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

상덕이가 털 보석점에는 보석이 총 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
input = sys.stdin.readline
import heapq

n, k = map(int, input().split())
jewels = []
for _ in range(n):
    heapq.heappush(jewels, list(map(int, input().split())))

weighs = []
for _ in range(k):
    weighs.append(int(input()))
weighs.sort()
# print(weighs)

answer = 0
tmp_jewels = []
for weigh in weighs:
    # print("aaaaaa", weigh)
    while jewels and weigh >= jewels[0][0]:
        # print("jewels: ", jewels, ", weigh: ", weigh, ", jewels[0][0]:", jewels[0][0])
        heapq.heappush(tmp_jewels, -heapq.heappop(jewels)[1])
        # print(tmp_jewels)
    if tmp_jewels:
        answer -= heapq.heappop(tmp_jewels)
        # print("answer: ", answer)
    elif not jewels:
        # print("not jewels: ", jewels)
        break

print(answer)