728x90
반응형
문제 바로가기
문제:
세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 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 heapq
import sys
from collections import deque
n, k = map(int, sys.stdin.readline().split(" "))
lst = []
for i in range(n):
m, v = map(int, sys.stdin.readline().split(" "))
heapq.heappush(lst, (m, v))
bag = deque(sorted([int(sys.stdin.readline()) for _ in range(k)]))
res = 0
while bag:
possible_weight = bag.popleft()
n_m, n_v = heapq.heappop(lst)
# 가방안에 들어감
if possible_weight >= n_m:
res += n_v
# 안 들어가면 도로 넣음
else:
heapq.heappush(lst, (n_m, n_v))
print(res)
작은 가방부터 뽑아내서 보석이 가방안에 들어가면 넣어주고 안 되면 다시 도로 넣어주는 단순하게 했는데
만약 무게가 같은경우가 문제가 됐다.
무게가 같은경우를 해결 한 후에도,
만약 가방이 10 일때
(5,5) , (7,10) 이면 뒤에께 들어와야하는데 앞에꺼로 정렬했기때문에 5,5 가 들어간다.
그래서 가방안에 들어가는 무게가 가지고 있는 value를 다 가지기로 했다.
정답
import heapq
import sys
from collections import deque
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
n, k = map(int, sys.stdin.readline().split(" "))
lst = []
for i in range(n):
m, v = map(int, sys.stdin.readline().split(" "))
heapq.heappush(lst, (m, -v))
bags = deque(sorted([int(sys.stdin.readline()) for _ in range(k)]))
res = []
result = 0
# 각 가방에 넣을 수 있는 최대 가치의 보석 담는다.
# 가방은 오름차순으로 작은 가방부터 넣을거 생각한다.
for bag in bags:
# 가방에 들어 갈 수 있는것들은 다 들어간다
while lst and bag >= lst[0][0]:
heapq.heappush(res, heapq.heappop(lst)[1])
# 그 중에 가장 큰 value값 가진것을 pop해준다.
# res를 for문 마다 선언을 안 해주는 이유는 어차피 가방에 무게가 작은 수서대로 올라가므로
# 굳이 안해주고, 다음 높은 밸류를 뽑아주면 된다.
if res:
result += - heapq.heappop(res)
elif not lst:
break
print(result)
반응형
댓글