[그리디] 백준 1202번: 보석 도둑 / 골드2

https://www.acmicpc.net/problem/1202

1202번: 보석 도둑

import collections
import heapq
import sys
n, m = map(int, sys.stdin.readline().split())

jem = collections.defaultdict(list)
for i in range(n):
    w, v = list(map(int, sys.stdin.readline().split()))
    jem[w].append(-v)

back = []
for i in range(m):
    back.append(int(input()))
back.sort()

q = []
cur = 0
answer = 0
for i in range(m):
    charge = back[i]
    if cur <= charge:
        for k in range(cur, charge+1):
            for elem in jem[k]:
                heapq.heappush(q, elem)
    if q:
        val = heapq.heappop(q)*-1
        answer += val
    cur = charge+1

print(answer)

그리디 문제로, 

가방을 작은 순서대로 정렬한 뒤, 각 가방이 선택가능한 리스트 중

가장 비싼것을 택하는 방식으로 부분 최적해를 찾았다.

 

중요한건 구현방식으로, 자칫하다간 시간 초과가 발생하기 쉬워 까다롭다.

가장 비싼것을 택해서 리스트에서 빼내 줘야 하는데,

일반적인 방법으로는 매우 비효율적일 수밖에 없고, 여기서는 우선순위 큐를 활용해야 한다.

heapq를 이용하여 최대힙을 구현하였다.