[알고리즘] BOJ 1202 보석도둑

[BOJ] 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 heapq
from sys import stdin

MV = [] # [ [무게, 가격], [무게, 가격], ... ]
C = [] # [ 가방의 용량, ... ]
TMP = [] # 임시 보관함
SUM = 0 # 보석 가격의 합의 최대값

N, K = map(int,stdin.readline().split())
for _ in range(N):
  MV.append(tuple(map(int,stdin.readline().split())))
for _ in range(K):
  C.append(int(stdin.readline()))

MV.sort()
C.sort()
idx = 0
for c in C: # 가방 용량 작은 순서대로
  while idx < N: 
    m, v = MV[idx]
    if m <= c: # 현재 보석의 무게가 가방의 용량과 같거나 작다면
      heapq.heappush(TMP,-v) # 우선순위큐에 추가
      idx += 1
    else:
      break # 현재 보석의 무게가 가방의 용랴옵다 크다면
  if TMP: # 현재 우선순위큐에 값이 존재한다면
    SUM += -heapq.heappop(TMP) # 보석 가격 추가
print(SUM)