1 minute read

문제

접근 방법

각 가방이 담을 수 있는 무게 한도 내에서 가장 값어치가 높은 보석을 담아야 한다. 따라서, Greedy를 사용해야 한다는 것을 알 수 있다.

따라서 각 가방을 기준으로 iterate하면서 가방이 들 수 있는 보석들 중에서 가장 값어치가 큰 보석을 찾아야 한다. 하지만 이렇게 naiive하게 iterate하면 300,000 x 300,000이 되어서 시간이 초과된다.

이를 해결하기 위해서 가방들을 무게 한도에 대해서 오름차순으로 정렬하고 보석들은 무게에 대해서 오름차순으로 정렬하였다. 가장 무게 한도가 낮은 가방부터 각 가방이 들 수 있는 무게 한도 내에 있는 보석들을 모두 우선순위 큐 (보석 가치를 우선순위로)에 입력하였다. 그 뒤에 무게 한도 내에서 가장 가치가 높은 보석을 heapq.heappop으로 구했다.

이렇게 하면 더 무거운 무게까지 담을 수 있는 가방은 우선순위 큐에 있는 보석들을 이미 다 담을 수 있기 때문에 괜찮다.

우선순위 큐를 활용하여 모든 상황을 체크해야 하는 상황을 효율적으로 하는 방법을 생각해내는 것이 어려웠다.

정답 코드


import sys
import heapq

input = sys.stdin.readline

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

jewels = []

for _ in range(n):
  m,v = map(int, input().split())
  jewels.append((m,v))

bags = []
for _ in range(k):
  b = int(input())
  bags.append(b)
    


"""
각 가방 무게에 들어갈 수 있는 가격이 제일 높은 애들의 가격을 더해야 한다.
"""

bags.sort()
jewels.sort()

prior_q = []

i=0
total = 0

for b in bags:
  while i<n and jewels[i][0] <= b:
    #현재 가방이 들 수 있는 무게 한도 내에서 모든 보석들을 추가
    heapq.heappush(prior_q, -jewels[i][1])
    i+=1

  if prior_q:
    #현재 가방이 들 수 있는 무게 한도 내에서 가장 값이 비싼 보석 뽑기
    total -= heapq.heappop(prior_q)

print(total)

You May Also Enjoy