보석 도둑 ( 1202 번 )

1202번: 보석 도둑

 

---

🧠 알고리즘

• 그리디(Greedy) + 최대 힙(Max Heap)

 

✔️ 동작 방식

• 보석들을 무게 기준 오름차순으로 정렬한다.
• 가방들을 수용 무게 기준 오름차순으로 정렬한다.
• 현재 가방이 담을 수 있는 보석들을 모두 후보 힙에 넣는다. (가격 기준, 최대 힙)
• 힙에서 가장 비싼 보석을 꺼내어 해당 가방에 담는다.
• 모든 가방을 확인한 후, 담은 보석들의 가격 합이 최대값이 된다.

---

 

🧾 코드

import sys, heapq
from collections import deque

def _main(n, k):
    answer = 0
    j = [tuple(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]
    b = [int(sys.stdin.readline().rstrip()) for _ in range(k)]

    j = deque(sorted(j, key=lambda x:x[0]))
    b.sort()

    size = []
    for now_bag in b:
        while j and j[0][0] <= now_bag:
            now_pop = j.popleft()
            heapq.heappush(size, -now_pop[1])

        if size:
            answer -= heapq.heappop(size)
    
    return answer


n, k = map(int, sys.stdin.readline().rstrip().split())
print(_main(n, k))

---

 

⏱️ 시간 복잡도

for now_bag in b : 가방을 순회하며 ( 선형 시간 복잡도 )
    내부 로직 >> 최대 힙 ( 로그 시간 복잡도 )

해당 알고리즘 시간 복잡도 : 선형 로그 시간 복잡도 ( O(n log n) )