[Baekjoon] 1202. ジュエリー泥棒

📚 質問する

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

📖 に答える

最大ヒップホップ、すなわち優先キューを使用して問題を解決します.
宝石とリュックサックは重量順に並んでいます.
そして小さなバッグから1つずつ巡り、大きなバッグや小さな宝石よりも価値を最大化します.
なければ入れないが,いくつかあればいくつか入れなさい.
詰め終わったら、バッグから価値のあるものを取り出して、次のバッグを探します.
バッグの重さが小さいことから、最大の価値を出します.

📒 コード#コード#

import heapq
import sys
input = sys.stdin.readline


n, k = map(int, input().split())
jams = sorted([list(map(int, input().split())) for _ in range(n)])  # 무게 순으로 정렬
bags = sorted([int(input()) for _ in range(k)])     # 무게 순으로 정렬

heap = []   # 가치가 큰 것부터 담을 최대 힙
s = 0
total = 0
for bag in bags:        # 무게가 작은 가방부터 순회
    while s < len(jams) and bag >= jams[s][0]:  # 현재 가방보다 무게가 작거나 같은 보석들을 순회
        heapq.heappush(heap, -jams[s][1])       # heap에 보석의 가치를 큰 순서대로 담는다.
        s += 1
    if heap:    # 힙에 가치가 가장 큰 것부터 가방 하나당 하나씩 꺼낸다.
        total += -heapq.heappop(heap)
print(total)

🔍 結果