백준 :: 1202번 보석 도둑 (Python)

문제 링크

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

1202번: 보석 도둑

 

접근 방식

먼저 각 가방에 담을 수 있는 보석의 최대 가격을 구하는 문제라서

보석을 가격 순으로 내림차순 정렬하고 가방마다 보석을 순회하면서 최대한 높은 가격의 보석을 담으려고 했다.

하지만 그렇게 생각하고 제약사항을 봤는데 보석과 가방의 개수가 각각 최대 30만..

내가 생각한 풀이의 시간복잡도를 계산해보면 30만의 제곱이라서 이 풀이는 패스..

그렇다면 전체를 순회하지 말고 최대값을 어떻게 뽑아낼 수 있을까..? → 여기가 핵심 !

우선순위큐 를 이용해서 풀면 될 것 같았다 !

각 가방에 대해 반복문을 돌면서 해당 가방이 담을 수 있는 무게까지 보석들을 우선순위 큐에다가 넣고,

(우선순위 큐는 MaxHeap 으로, 큐에 넣을 때는 보석의 가격으로 !)

다 넣었으면 루트 노드만 pop 하는 식으로 구현하면 바로 담을 수 있는 최대 가격을 알 수 있다.

여기서 시간복잡도를 계산해보자.

가방을 전체 순회하는 데에 O(N), 우선순위 큐에서는 삽입, 삭제 시 O(logN) 이니까

O(NlogN) 이 걸릴 것이다.

이제 코드로 옮겨보자 !

풀이 코드

import sys
import heapq
from collections import deque

def input():
    return sys.stdin.readline().rstrip()

N, K = map(int, input().split())
gems = []

for _ in range(N):
    M, V = map(int, input().split())
    gems.append((M, V))

bags = []
for _ in range(K):
    bags.append(int(input()))

# 보석 무게 오름차순 정렬
gems.sort(key = lambda x : (x[0], -x[1]))
gems = deque(gems)
bags.sort()
result = 0
queue = []

for bag in bags:
    while gems and gems[0][0] <= bag: # 가방에 담을 수 있는 무게보다 커지면 break
        gem = gems.popleft()
        heapq.heappush(queue, -gem[1])
    if queue:
        result -= heapq.heappop(queue)

print(result)

치열한 고민의 흔적..

끝.