1202보석도둑

import sysimport heapqinput = sys.stdin.readlinejul = []
n, k = map(int, input().split())for _ in range(n):
    heapq.heappush(jul, [*map(int, input().split())])
bag = [int(input()) for _ in range(k)]  # 작은순서대로 정렬bag.sort()h = []answer = 0
for b in bag:    while jul and jul[0][0] <= b:  # 가방에 담을수 있는 모든 보석
        heapq.heappush(h, -heapq.heappop(jul)[1])  # 무게만 담기
    if h:  # 만일 담을수 있는 보석이 있다면
        answer -= heapq.heappop(h)  # 현재 가방에 담을 수 있는 보석 중 가장 가치높은 보석만 꺼내기
print(answer)

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

1202번: 보석 도둑첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ciwww.acmicpc.net

다른사람들 풀이를 참고했다.

맨 처음에는 그냥 다 탐색해서 풀었는데, 당연히 시간초과가 났다.

우리가 구하려는 것은 ‘가장작은 가방에 들어갈 수 있는 최대 가치의 보석’이다.

따라서 가장 작은 가방부터 시작한다.

임시 최대힙인 h를 만들어 놓고, (최대힙)

보석은 무계순으로 정렬해 놓는다.

보석의 첫번째 원소가 (가장 가벼운 원소가) 가방보다 무거울 때까지,

보석의 첫번째 원소를 하나씩 pop하고, 임시 최대힙에 push한다(가치만).

이 과정이 끝나면, h에는 ‘현재 가방에 들어갈 수 있는 모든 보석’ 이 가치순으로 역정렬되어있을 것이다.

그중 가장 큰 보석을 pop해준다.

이 과정을 반복하다 보면, 결국 각 가방에 가치가 가장 큰 보석만 들어가게 되므로, 이를 더해준다.