BOJ #1202 보석 도둑

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

BOJ #1202 보석 도둑

문제 풀이

보석을 무게 순으로 정렬하고 가방도 무게 순으로 정렬한 뒤 가방의 무게보다 작거나 같은 보석들을 뽑아 우선순위 큐에 넣고 뽑으면 해당 가방에 넣을 수 있는 보석들 중 가장 비싼 보석이 될 것이다.

• 보석을 입력받고 무게 순으로 정렬한 뒤 queue에 넣는다.
• 가방을 입력받고 무게 순으로 정렬한다.
• 각 가방에 대해 무게 순으로 정렬한 보석 큐를 대상으로 현재 탐색 가방의 용량 이하라면 우선순위 큐에 가치를 기준으로 최대 힙을 구성한다.
• 위의 과정을 끝내고 큐에 원소가 존재한다면 루트를 뽑아 정답에 더해준다.
• 모든 가방에 대해 위 과정을 수행한다.

python 코드

import sys
from collections import deque
from heapq import heappush, heappop
input = sys.stdin.readline

def solve():
    N, K = map(int, input().split())
    jewels = []
    bags = []
    for _ in range(N):
        m, v = map(int, input().split())
        jewels.append((m, v))
    for _ in range(K):
        bags.append(int(input()))
    jewels.sort()
    jewels = deque(jewels)
    bags.sort()
    q = []
    sol = 0
    for bag in bags:
        while jewels and jewels[0][0] <= bag:
            m, v = jewels.popleft()
            heappush(q, (-v, m, v))
        if q:
            d, m, v = heappop(q)
            sol += v
    return sol
print(solve())