백준 1202 보석 도둑

문제

👀 문제 사이트 : https://www.acmicpc.net/problem/1202

풀이

난이도 : Gold II

• 이 문제는 greedy 알고리즘과 priority queue를 이용하여 해결하였다.

1. 보석과 가방을 입력받은 후에 정렬을 한다. (보석은 무게 순으로 참조할 것이기 때문에 무게 순으로 정렬)
2. 가방 안에는 한 개의 보석 밖에 들어갈 수 없으므로 조금 쉽게 접근할 수 있는데, 가방에 들어갈 수 있는 보석의 무게가 작은 것부터 참조하면서 그 안에 들어갈 수 있는 보석들 중에서 가장 가치가 높은 보석을 한 개만 고르면 된다.
3. 따라서 가방의 무게보다 작은 보석들을 모두 우선순위 큐에 담아놓고, 가장 높은 가치의 보석을 하나씩 꺼내기만 하면 된다.
4. 여기서 우선순위 큐는 비우지 않는데, 가방을 크기 순으로 정렬해두었기 때문에 다음 가방을 참조할 때, 이 큐에 들어있는 모든 보석들의 무게는 다 담을 수 있기 때문이다.

코드

  from sys import stdin
  import heapq

  input = stdin.readline

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

  jew = []
  bag = []
  q = []

  for _ in range(n):
      jew.append(list(map(int, input().split())))

  for _ in range(k):
      bag.append(int(input()))

  bag.sort()
  jew.sort()

  result = 0
  index = 0
  for b in bag:
      while index < len(jew) and jew[index][0] <= b:
          heapq.heappush(q, -jew[index][1])
          index = index + 1
      if q:
          result = result + (-heapq.heappop(q))
  print(result)