문제
루팡은 배낭을 하나 메고 은행금고에 들어왔다. 금고 안에는 값비싼 금, 은, 백금 등의 귀금속 덩어리가 잔뜩 들어있다. 배낭은 W ㎏까지 담을 수 있다. 각 금속의 무게와 무게당 가격이 주어졌을 때 배낭을 채울 수 있는 가장 값비싼 가격은 얼마인가?
루팡은 전동톱을 가지고 있으며 귀금속은 톱으로 자르면 잘려진 부분의 무게만큼 가치를 가진다.
입력
첫 번째 줄에 배낭의 무게 W와 귀금속의 종류 N이 주어진다.번째 줄에는 번째 금속의 무게 와 무게당 가격 가 주어진다.
입력은 다음 조건을 만족한다.
인 정수
인 정수
인 정수
출력
첫 번째 줄에 배낭에 담을 수 있는 가장 비싼 가격을 출력하라.
예시
입력
100 2
90 1
70 2
Plain Text
복사
출력
170
Plain Text
복사
정답
import sys
import heapq
W, N = list(map(int, sys.stdin.readline().split()))
hq = [] # (-가격, 무게)를 담을 힙
for _ in range(N):
m, p = list(map(int, sys.stdin.readline().split()))
heapq.heappush(hq, (-p, m)) # 가격이 높은 순으로 정렬되어야 하기 때문에 -p를 붙여서 넣는다.
answer = 0
while (W > 0) and (len(hq)>0): # 더 담을 수 있는 무게가 있고 보석이 남아있는 경우
current = heapq.heappop(hq) # 가장 값비싼 보석 pop
if current[1] <= W: # 보석의 무게가 남은 무게보다 작거나 같은 경우
answer += current[1]*(-current[0]) # 보석을 모두 담음 -> 보석 무게 * 보석 가격 만큼 더해준다.
W -= current[1] # 가져간 보석 무게만큼 남은 무게에서 빼줌
else: # 보석의 무게가 남은 무게보다 큰 경우 -> 남은 무게만큼만 가져가야 함.
answer += W*(-current[0]) # 남은 무게 * 보석 가격 만큼 더해준다.
W = 0 # 남은 무게 = 0
print(answer)
Python
복사
풀이
•
힙을 이용하여 풀 수 있다.
•
우선 포인트는 보석을 자를 수 있기 때문에 값어치가 많이 나가는 보석순으로 정렬해서 계속해서 담아야 한다는 점이다.
•
따라서 (-가격, 무게)를 담는 힙을 만든다.
•
이때 -가격인 이유는 가격에 따라서 내림차순 정렬되어야 하기 때문.
hq = [] # (-가격, 무게)를 담을 힙
for _ in range(N):
m, p = list(map(int, sys.stdin.readline().split()))
heapq.heappush(hq, (-p, m)) # 가격이 높은 순으로 정렬되어야 하기 때문에 -p를 붙여서 넣는다.
Python
복사
•
그 다음 더 담을 수 있는 무게가 있고 보석이 남아있는 경우 가장 값어치가 높은 보석부터 힙에서 꺼내서 담는다.
answer = 0
while (W > 0) and (len(hq)>0): # 더 담을 수 있는 무게가 있고 보석이 남아있는 경우
current = heapq.heappop(hq) # 가장 값비싼 보석 pop
Python
복사
•
만약 보석의 무게가 남은 무게보다 작거나 같은 경우 보석을 모두 담고 남은 무게를 가져간 보석의 무게만큼 빼준다. 그리고 보석의 무게에 보석 가격만큼 더해서 총 값어치에 + 해준다.
if current[1] <= W: # 보석의 무게가 남은 무게보다 작거나 같은 경우
answer += current[1]*(-current[0]) # 보석을 모두 담음 -> 보석 무게 * 보석 가격 만큼 더해준다.
W -= current[1] # 가져간 보석 무게만큼 남은 무게에서 빼줌
Python
복사
•
만약 보석의 무게가 남은 무게보다 큰 경우 남은 무게만큼만 가져가고 남은 무게는 0이 된다. 이때 더해지는 값어치는 남은 무게 * 보석 가격
else: # 보석의 무게가 남은 무게보다 큰 경우 -> 남은 무게만큼만 가져가야 함.
answer += W*(-current[0]) # 남은 무게 * 보석 가격 만큼 더해준다.
W = 0 # 남은 무게 = 0
Python
복사
•
마지막으로 총 값어치를 프린트한다.
print(answer)
Python
복사