https://www.acmicpc.net/problem/1202
시간 1초, 메모리 256MB
input :
- N K(1 ≤ N, K ≤ 300,000)
- Mi Vi(0 ≤ Mi, Vi ≤ 1,000,000)
- Ci(1 ≤ Ci ≤ 100,000,000)
output :
- 보석 가격의 합의 최댓값을 출력
조건 :
- 가방에는 최대 한 개의 보석만 넣을 수 있다.
생각보단 간단한? 그걸 생각하기 까지 예제가 적어서(?) 좀 힘들었던 거 같다.
지난 번에 문제를 보았을 때는 그냥 풀기 싫어서 때려치웠었다 ㅋㅋㅋㅋㅋㅋ
일단 예제가
3 2
1 65
5 23
2 99
10
2
인데 여기에다가 9 250 짜리 보석을 하나 더 넣어보자.
그렇다면 우리가 2일 때 집어갈 수 있는 것은
1 65 / 2 99
두 가지이다. 이 중에서 더 가치가 큰 것을 가져가고.
10일 때 는
1 65 / 9 250
이 된다. 여기서도 더 가치가 큰 것을 가져간다.
그렇다면 우리가 해야 되는 것은 무엇인가??
가방의 무게를 오름차순으로 정렬 하고 그것 보다 작은 모든 보석들을 옮긴다. 그리고 이를 가치 기준으로 내림차순 정렬 해서 가장 큰 놈을 가지고 나온다.
이를 가장 빠르게 할 수 있는 것은 우선순위 큐이다.
그래서 우리는 원래 보석 배열에서 이놈들 자체를 빼버려야 하기 때문에 시작부터 우선순위 큐를 쓰는 것이 편하다.
** 추가적인 시간 복잡도 절약을 위해
마지막에 capable_jewel 배열이 존재하지 않고, jewel 배열도 존재하지 않는다면 더이상 가져갈 게 없다는 것으로 break를 걸어주자.
import sys
from heapq import heappop, heappush
n, k = map(int, sys.stdin.readline().split())
jewel = []
beg = []
capable_jewel = []
for i in range(n):
m, v = map(int, sys.stdin.readline().split())
heappush(jewel, (m, v))
for i in range(k):
c = int(sys.stdin.readline())
heappush(beg, c)
ans = 0
for i in range(k):
limit = heappop(beg)
while jewel and limit >= jewel[0][0]:
wei, val = heappop(jewel)
heappush(capable_jewel, (-val, wei))
if capable_jewel:
ans -= heappop(capable_jewel)[0]
elif not jewel:
break
print(ans)
