BaekJoon1202_보석도둑

문제

풀이

이 문제는 가장 비싼 보석을 담아가며 풀면 되는데 이때 용량이 가장 작은 가방에 먼저 보석을 담아가면 답을 찾을 수 있다. 이때 가방을 용량 순서로 정렬한 뒤 차근차근 풀어나가야 답을 구할 수 있다.
이 아이디를 구현할 땐 최대힙과 최소힙을 사용하여 풀어야 하는데 나는 어거지로 풀려하다보니 답은 나오지만 시간초과가 나오는 결과를 맞이했다. 최대힙과 최소힙은 다시한번 공부해서 정리하여 올릴 예정이다.

틀린 코드

n, k = map(int,input().split())
jew = []
for _ in range(n):
   jew.append(tuple(map(int, input().split())))
jew.sort(key = lambda x: -x[1])
C=[]
for _  in range(k):
   C.append(int(input()))

C.sort(reverse=True)
temp = []
answer = 0

while(C):
   for i in range(n):
       for j in C:
           if jew[i][0] > j:
               continue
           else:
               C.remove(j)
               temp.append(jew[i][1])
               break
answer += sum(temp)
print(answer)

정답 코드

# 정답 코드
import heapq

n, k = map(int,input().split())
jew = []
for _ in range(n):
   heapq.heappush(jew, list(map(int,input().split())))

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

C.sort()
temp = []
answer = 0

for i in C:
   while jew and i >= jew[0][0]:
       heapq.heappush(temp, -heapq.heappop(jew)[1])
   if temp:
       answer -= heapq.heappop(temp)
   elif not jew:
       break

print(answer)