[백준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)

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

출력

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

예제 입력 1

3 2
1 65
5 23
2 99
10
2

예제 출력 1

164

나의 풀이

이 문제는 그리디 기법을 힙 구조를 사용하면 되는 문제였다. 단순히 이중 for문으로 문제를 풀려고하면 시간 복잡도가 n^2이지만 힙을 사용하면 nlogn으로 줄일 수 있다.

• 우선 가방의 무게와 보석의 무게를 오름차순으로 정렬을 한다. (파이썬 기존 sort는 퀵소트로 nlogn이다.)
• 가방의 수만큼 반복을 한다.
  • 각 가방의 반복에서 가방에 들어갈 수 있는 보석들의 가격을 최대힙에 push한다.
  • 바로 위의 과정이 끝나면 최대힙에서 pop(가격의 최대값)한 값을 정답을 담는 변수에 더해준다.

코드

# 보석 도둑
import heapq

n, k = map(int, input().split())
visited = [False for _ in range(n)]

jewelry = [list(map(int, input().split())) for _ in range(n)]
bags = [int(input()) for _ in range(k)]

jewelry.sort()
bags.sort()

answer = 0
heap = []
j = 0
for i in range(k):
    while j < n:
        if jewelry[j][0] <= bags[i]:
            heapq.heappush(heap, (-1) * jewelry[j][1])
            j += 1
        else:
            break

    if heap:
        answer += (-1) * heapq.heappop(heap)

print(answer)