Algorithm/Greedy

[Python - Greedy] 1202 보석 도둑

턴태 2022. 9. 8. 13:18

📌 문제

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

 

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

 

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

📌 입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

 

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

 

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

 

모든 숫자는 양의 정수이다.

📌 출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

📌 문제 풀이

👨‍🏫 접근

일단 중요한 것은 가방에는 보석을 하나만 넣을 수 있으며 일정 무게 이하만 넣을 수 있다는 것이다. 그렇다면, 해당 가방의 무게를 중심으로 해서 그 가방에 넣을 수 있는 보석들 중에서 가장 가치있는 보석을 담아야 최대로 보석을 훔칠 수 있다.

 

그렇기 때문에 가방과 보석을 정렬해서 알고리즘을 시작해야 한다. 그리고 반복의 기준은 가방이다. 가방에 보석을 담아야 훔칠 수 있어서 보석보다 가방이 중심이 되어 반복문을 진행해야 한다.

 

그렇게 가방을 중심으로 세운 다음에는 보석을 찾아나선다. 해당 가방은 자신보다 무게가 같거나 가벼운 보석을 넣을 수 있다. 그래서 자신보다 가벼운 보석들은 모두 일정한 공간에 넣어둔다. 그 이후에 자신보다 무거운 보석을 발견하면 멈춰서, 현재 어떤 보석이 가장 가치있는지를 찾아내서 결괏값에 넣으면 되는 것이다. 이때, 가장 가치있는 보석은 우선순위 큐를 사용해서 쉽게 뽑아낼 수 있다.

 

이렇게 하면 다음 가방을 기준으로 할 때, 이전 가방보다 현재 가방이 가용 무게가 같거나 더 무겁기 때문에 이전 가방에서 멈춘 보석에서부터 다시 시작해서 일정한 공간에 넣는 작업을 반복한다. 그렇게 하여 모든 가방을 순환하면 가격의 최대를 얻을 수 있다.

👨‍🏫 문제 풀이

📄 전체 코드

import sys
import heapq
input = sys.stdin.readline

# 포커스는 보석의 무게
# 보석의 가치를 우선순위 큐로 뽑아내면서 최댓값을 찾아나서면 됨.
n, k = map(int, input().split())

gems = sorted(list(map(int, input().split())) for _ in range(n))
bags = sorted(int(input()) for _ in range(k))
q = []
ans = 0
j = 0

for i in range(k):
    while (j < n) and (gems[j][0] <= bags[i]):
        heapq.heappush(q, -gems[j][1])
        j += 1

    if q:
        ans -= heapq.heappop(q)

print(ans)

📄 준비

import sys
import heapq
input = sys.stdin.readline

# 포커스는 보석의 무게
# 보석의 가치를 우선순위 큐로 뽑아내면서 최댓값을 찾아나서면 됨.
n, k = map(int, input().split())

gems = sorted(list(map(int, input().split())) for _ in range(n))
bags = sorted(int(input()) for _ in range(k))
q = []
ans = 0
j = 0

각각 보석과 가방을 오름차순으로 정렬해준다. 이때 q는 탐색이 종료된 보석을 담을 우선순위 큐이고, j는 그 보석을 탐색하는 인덱스 값이다.

📄 풀이

for i in range(k):
    while (j < n) and (gems[j][0] <= bags[i]):
        heapq.heappush(q, -gems[j][1])
        j += 1

    if q:
        ans -= heapq.heappop(q)

print(ans)

먼저 모든 보석을 순환하기 전까지 반복하고, 보석 무게가 같거나 더 가벼울 때 그 보석은 가방에 담을 수 있는 보석이기 때문에 우선순위 큐에 값을 넣어준다. 최대 힙을 구현하기 위해서 값을 넣을 때는 -값을 넣어줬다.

 

보석을 탐색하다가 더 무거운 보석을 발견하면 거기서 탐색을 멈춘다. 그 이후에 우선순위 큐에 값이 있으면(조건을 충족하는 보석을 찾았다면) 정답에 값을 더해준다. 이때, 우선순위 큐에 음의 값을 넣었기 때문에 다시 마이너스 연산자를 사용한다.

📌 총평

 

너무 어려웠다. 어떤 것을 우선순위 큐로 구현할지 갈피를 못잡아서 오래 걸렸다. 우선순위 큐에 값을 넣을 때는, 최댓값이 될 값을 넣도록 하자.

 

저작자표시 비영리