보석 도둑 (1202번) - 백준 (BOJ)

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

1202번: 보석 도둑

 

 

백준 - 보석 도둑 (LOPOV) (1202번)

난이도 : Gold 2

알고리즘 : Priority Queue & Sorting

풀이 소요 시간 : 90분

Time Complexity : O( O(N * log(N) )

 

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


if __name__ == '__main__':
    N, K = map(int, input().split())
    js = []
    for _ in range(N):
        m, v = map(int, input().split())
        js.append((-v, m))
    js.sort(key=lambda x: -x[1])
    
    total = 0
    pq = []
    for c in sorted(int(input()) for _ in range(K)):
        while js and js[-1][1] <= c:
            heappush(pq, js.pop())
        if pq:
            v, _ = heappop(pq)
            total -= v
    
    print(total)

 

가방들을 용량 순서대로 정렬하고,

보석들은 무게 순서대로 정렬해서

 

가방을 하나씩 살펴보면서

현재 가방 용량보다 작거나 같은 무게의 보석들을

보석 가치 기준으로 Priority Queue에 넣어둔다.

 

그리고 가장 가치가 높은 보석 하나를 Priority Queue에서 꺼내면,

그 보석이 현재 가방에 넣을 보석이다.

 

---

 

아이디어 떠올리기는 어렵지만,

방법만 알면 구현 자체는 쉬운 문제.

 

앞으로 비슷한 유형의 문제를 풀 때

많은 힌트를 얻을 수 있는 좋은 문제였다.