📌 문제
세계적인 도둑 상덕이는 보석점을 털기로 결심했다.
상덕이가 털 보석점에는 보석이 총 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)
먼저 모든 보석을 순환하기 전까지 반복하고, 보석 무게가 같거나 더 가벼울 때 그 보석은 가방에 담을 수 있는 보석이기 때문에 우선순위 큐에 값을 넣어준다. 최대 힙을 구현하기 위해서 값을 넣을 때는 -값을 넣어줬다.
보석을 탐색하다가 더 무거운 보석을 발견하면 거기서 탐색을 멈춘다. 그 이후에 우선순위 큐에 값이 있으면(조건을 충족하는 보석을 찾았다면) 정답에 값을 더해준다. 이때, 우선순위 큐에 음의 값을 넣었기 때문에 다시 마이너스 연산자를 사용한다.
📌 총평
너무 어려웠다. 어떤 것을 우선순위 큐로 구현할지 갈피를 못잡아서 오래 걸렸다. 우선순위 큐에 값을 넣을 때는, 최댓값이 될 값을 넣도록 하자.
'Algorithm > Greedy' 카테고리의 다른 글
[Python - Greedy, Priority Queue] 1826 연료 채우기 (0) | 2022.09.09 |
---|---|
[Python - Greedy, Bipartite Matching] 9576 책 나눠주기 (0) | 2022.09.08 |
[Python - Greedy] 1931 회의실 배정 (0) | 2022.09.02 |
[Python] 1946 신입 사원 (0) | 2022.06.20 |
[Python] 1789 수들의 합 (0) | 2022.06.20 |