[ baekjoon ] 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)

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

출력

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

## 1202. 보석 도둑
import sys
import heapq
input = sys.stdin.readline

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

info = [] # 보석의 정보(무게, 가격)
for _ in range(n):
  info.append(list(map(int, input().split())))

max_weight = []
for _ in range(k):
  max_weight.append(int(input())) # 가방에 담을 수 있는 최대 무게 c

# 상덕이가 훔칠 수 있는 보석의 최대 가격 구하라
info.sort()
max_weight.sort()

heap = [] # 최대힙 만들자
result = 0

# 가방 개수만큼 반복하자
jew = 0
for weight in max_weight:
  while jew < n:
    if weight >= info[jew][0]:
      heapq.heappush(heap, (-1) * info[jew][1]) # 최대힙 만들기 위해 -1 곱함
      jew += 1
    else:
      break
        
  if heap:
    result += (-1) * heapq.heappop(heap)

print(result)

처음엔 heapq를 써야하나? 생각했지만 나는 info, max_weight를 내림차순으로 정렬하려고 했기 때문에,
기본 최소힙을 쓰는 heapq말고 deque를 이용해 pop을 하려고 했다(max_weight) 하지만 7%에서 계속 실패했다
그래서 계속 하다가 안돼서 찾아보니 heapq 최대힙으로 구성해서 문제를 푸는 것이었다
우선순위큐 라이브러리는 따로 있는 것 같았지만 일단 아는 heapq를 이용했다.

처음에 반복문을

  while weight >= info[jew][0]: # 가방 무게가 더 클때까지만 heappush 하자
    heapq.heappush(heap, (-1) * info[jew][1])
    if jew == n - 1: break
    jew += 1
    if heap:
      result += (-1) * heapq.heappop(heap)

위의 코드로 작성했는데 7%에서 실패했다.
가방의 개수를 기준으로 먼저 for문을 돌려야 한다. 가방 K개를 다 반복하면 종료한다. 그 후 while문에서 보석을 모두 검사하면 종료되게끔 조건을 작성한다.

이 문제를 풀면서 heapq에 대해 더 정리해봐야 할 듯하다! 기본 최소힙으로 구성됐지만 최대힙으로 할 수 있는 거 정리해놔야지!