문제
문제 해설
가장 먼저, 어떻게 하면 최대한 많은 가격을 이끌어 낼 수 있을지 생각해야합니다.
가방 하나당 하나의 보석만 훔칠 수 있으므로 2가지 방법을 생각했습니다.
1. 최대한 비싼 보석을 최대한 가벼운 가방에 넣는다.
2. 최대한 가벼운 보석을 최대한 가벼운 가방에 넣는다.
2번의 경우 말도 안되서 바로 포기했고, 1번을 어떻게 할까 생각하다가 아무리 생각해도 시간 초과가 날 것 같아 최대힙과 최소힙을 이용하는 방법을 채택했습니다.
- 가방을 오름차순 정렬합니다.(klogk)
- 보석의 무게를 기준으로하는 최소힙을 만들어 무게와 가치를 저장합니다.(nlogn)
- 현재 가방에 담을 수 있는 보석을 모두 꺼냅니다.
- 꺼낸 보석은 가치만을 담고 있는 최대힙에 저장합니다.
- heappop() -> 현재 담을 수 있는 보석 중 가장 가치있는 물건입니다.
- 가방을 모두 사용하거나 보석을 담을 수 없을때 까지 반복합니다.(nlogn)
참고로 파이썬의 heapq같은 경우 java의 PriorityQueue와 같은 자료구조가 아니고 리스트를 힙의 형태로 사용할 수 있는 라이브러리이기 때문에 그냥 리스트처럼 인덱스 접근이 가능합니다.
풀이 코드
import sys
import heapq
input = sys.stdin.readline
n, k = map(int, input().split())
items = []
bag = []
candi = []
answer = 0
for _ in range(n):
# 보석 무게 기준 최소 힙 삽입
heapq.heappush(items, list(map(int, input().split())))
for _ in range(k):
bag.append(int(input()))
# 가방 오름차순 정렬
bag = sorted(bag)
for cap in bag:
# 가방 작은거 부터 꺼내면서 그 가방에 들어가는 보석일단 다 꺼냄.
# 꺼내서 값을 기준으로 최대힙에 넣음
while items and items[0][0] <= cap:
heapq.heappush(candi, -heapq.heappop(items)[1])
# candi에 현재 가방에 들어갈 수 있는 보석 다들어있음.(최대힙)
# 이 중 하나 빼면 됨.
if candi:
answer += abs(heapq.heappop(candi))
print(answer)