[백준] 1202. 보석 도둑/Python - Gold2

❓문제

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

성능 요약

메모리: 107448 KB, 시간: 1752 ms

분류

자료 구조, 그리디 알고리즘, 우선순위 큐, 정렬

 

문제 설명

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

✍🏻풀이

처음에는 각 보석을 최대힙으로 리스트에 넣고, 가방을 무거운 순으로 정렬하였다. 그러나 이런 경우 보석이 무게대로 정렬되어있는 것이 아니기에 큰 가방에 이미 보석이 들어간 경우가 생겨 우선순위가 두번째인 보석이 오히려 못 들어가게 되는 경우가 생겼다.

그러므로 각 보석을 무게를 기준으로 정렬하고 가방도 오름차순으로 정렬하였다. 각 보석을 가방에 넣을 수 있는지 확인하면 가능한 보석들을 possible 리스트에 최대힙으로 넣는다. 이 때, 해당 보석들은 가방에 넣을 수 있는 보석들로 우리는 보석의 가치만 리스트에 넣으면 된다. 더 이상 해당 가방에 넣을 수 있는 보석이 없다면 가능한 보석들 중에서 가장 가치가 큰 보석을 res에 더하면 된다. 더 이상 가방에 넣을 수 있는 보석이 없고 남은 보석도 없다면 반복문을 나와 결과값을 출력하면 된다.

💻코드

import sys
from heapq import heappush, heappop

input = sys.stdin.readline

N, K = map(int, input().split())
jewelry = [list(map(int, input().split())) for _ in range(N)]
jewelry.sort()

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

possible = []
res = 0
for b in bags:
    while jewelry and jewelry[0][0] <= b:
        heappush(possible, -heappop(jewelry)[1])
    if possible:
        res += -heappop(possible)
    elif not jewelry:
        break

print(res)

📍후기

자료구조를 이용해서 간단한 문제는 풀 수 있지만 아직 어떤 알고리즘을 적용해야 하는지는 감을 잡지 못한 것 같다ㅠ