문제:
세계적인 도둑 상덕이는 보석점을 털기로 결심했다.
상덕이가 털 보석점에는 보석이 총 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)
모든 숫자는 양의 정수이다.
출력:
첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.
풀이방법:
우선순위 큐(heapq)를 사용해서 가방에 최대한 비싼 보석을 그리디하게 넣는다 생각하면 된다. 따라서 보석의 정보들을 무게가 가벼운 순으로 heapq를 통해서 정렬하고, 가방도 오름차순으로 정렬을 한다.
정렬을 마친 뒤에 가벼운 가방으로부터 시작하여 해당 가방에 넣을 수 있는 보석들을 최대힙으로 다시 구현을 한 뒤에 그 최대힙에서 가장 큰 값을 뽑아 answer에 더해준다. 이와 같은 과정들을 모든 가방에 대해 수행을 하며, 최대힙과 최소힙은 계속해서 누적해서 사용하도록 한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
import heapq
import copy
N, K = map(int,input().split())
h = []
for _ in range(N):
m, v = map(int,input().split())
heapq.heappush(h,(m,v))
bags = []
for _ in range(K):
bags.append(int(input()))
bags.sort()
answer = 0
ans = []
for bag in bags:
while (h and h[0][0]<=bag):
heapq.heappush(ans,-heapq.heappop(h)[-1])
if ans:
answer += -heapq.heappop(ans)
elif not h:
break
print(answer)
|
cs |
문제링크:
https://www.acmicpc.net/problem/1202
1202번: 보석 도둑
첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci
www.acmicpc.net
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]1722. 순열의 순서 (0) | 2021.09.27 |
|---|---|
| [BOJ]1351. 무한 수열 (0) | 2021.09.24 |
| [BOJ]1057. 토너먼트 (0) | 2021.09.16 |
| [BOJ] 14890. 경사로 (0) | 2021.09.15 |
| [BOJ]14719. 빗물 (0) | 2021.09.14 |