[소프티어] 금고털이
T
TikaToka
이 문제 같은 경우는 그냥 직관적으로 풀어도 통과하기도 한다 (실행 때 마다의 미세한 시간 차이 때문에)
Naive Sol
import sys
w, n = map(int, input().split())
golds = []
for i in range(n):
golds.append(list(map(int, input().split())))
golds.sort(key=lambda x: -x[1])
gram = 0
answer = 0
for i in golds:
if gram >= w:
break
if gram + i[0] <= w:
gram += i[0]
answer += i[0] * i[1]
else:
temp = w - gram
gram = w
answer += temp * i[1]
print(answer)
하지만 우리는 최대부터 고려하면 되기 때문에, 그때의 최대만을 계속 뽑아낼 수 있는 heap을 쓸 수 있다
Sol
import heapq
w, n = map(int, input().split())
# 1g당 금 가격의 역순으로 최대 힙 구성
golds = []
for _ in range(n):
weight, price = map(int, input().split())
heapq.heappush(golds, (-price, weight))
gram = 0
answer = 0
while golds and gram < w:
neg_price, weight = heapq.heappop(golds)
price = -neg_price # 원래의 가격 복원
if gram + weight <= w:
gram += weight
answer += weight * price
else:
remaining = w - gram
answer += remaining * price
break
print(answer)
