문제 설명
문제
세계적인 도둑 상덕이는 보석점을 털기로 결심했다.
상덕이가 털 보석점에는 보석이 총 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)
모든 숫자는 양의 정수이다.
출력
첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.
문제링크
전체 코드
import heapq
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
arr = []
for _ in range(n):
m, v = map(int, input().split())
heapq.heappush(arr,[m,v])
c = []
for _ in range(k):
heapq.heappush(c, int(input()))
result = 0
capable_gem = []
for i in range(k):
top = heapq.heappop(c)
while arr and top >= arr[0][0]:
[m, v] = heapq.heappop(arr)
heapq.heappush(capable_gem, -v)
if capable_gem:
result -= heapq.heappop(capable_gem)
elif not arr:
break
print(result)해결 방법
내가 푼 방법은 시간초과가 나서 다른 사람의 풀이를 보고 코드를 옮겼다 그 사람의 풀이를 출처와 함께 남기겠다.
우선 순위 큐를 구현한 최대 최소힙을 통해 풀이하였다. 이를 모른다면 공부를 먼저 하고오길 추천한다.
현재 가장 작은 무게를 수용할 수 있는 가방(=capacity) 이하의 모든 보석(capable_gem) 중 가장 값이 큰 것을 뽑아내고 이를 가방이 끝날 때 까지 반복하는 것이 목표다.
다음과 같은 알고리즘을 따른다.
1) Bag의 최솟값을 heappop 해준다. 해당 Bag은 현재의 capacity 즉, 수용량이 된다.
2) 수용량 이하 무게의 모든 보석 Gem을 capable_gem에 무게를 제외한 값만 heappush하여 넣어준다.
3) capacity이하의 모든 무게의 보석을 꺼냈으면 capable_gem(최대 힙)중 가장 큰 값을 heappop하여 꺼낸 뒤 bag에 넣어준다(total_value에 추가한다).
4) beg이 남았지만 gem이 없을 경우(:모든 gem이 capable_gem일 경우) capable_gem에서 heappop하여 현재 bag에 차례대로 넣어준다.
5) 1~4를 반복한 뒤 bag이 더 이상 없거나, gem과 capable_Gem 모두가 비었으면 while문을 끝낸다.
