[Softeer] 금고털이

문제

루팡은 배낭을 하나 메고 은행금고에 들어왔다. 금고 안에는 값비싼 금, 은, 백금 등의 귀금속 덩어리가 잔뜩 들어있다. 배낭은 W ㎏까지 담을 수 있다.

 

각 금속의 무게와 무게당 가격이 주어졌을 때 배낭을 채울 수 있는 가장 값비싼 가격은 얼마인가?

 

루팡은 전동톱을 가지고 있으며 귀금속은 톱으로 자르면 잘려진 부분의 무게만큼 가치를 가진다.

제약조건

1 ≤ N ≤ 106인 정수

1 ≤ W ≤ 104인 정수

1 ≤ Mi, Pi ≤ 104인 정수

입력형식

첫 번째 줄에 배낭의 무게 W와 귀금속의 종류 N이 주어진다. i + 1 (1 ≤ i ≤ N)번째 줄에는 i번째 금속의 무게 Mi와 무게당 가격 Pi가 주어진다.

출력형식

첫 번째 줄에 배낭에 담을 수 있는 가장 비싼 가격을 출력하라.

입력예제1

100 2 90 1 70 2

출력예제1

170

---

풀이

풀이1 (오답)

import sys
input = sys.stdin.readline

w, n = map(int, input().split())
metals = []

for _ in range(n):
  m, p = map(int, input().split())
  metals.append([p, m])

metals = sorted(metals, reverse=True)
result = 0

for price, weight in metals:
  if w > weight:
      result += (weight * price)
      w -= weight
  else:
    result += (w * price)
    break

print(result)

 

처음엔 문제도 아예 잘못 이해해서 예제 답도 왜 저러지 하면서 헤맸다.

그리고 나서는 잘 풀었는데 왜이러지 싶어서 한참 고민했다.

 

---

풀이2

import sys
input = sys.stdin.readline

w, n = map(int, input().split())
metals = [list(map(int,input().split())) for _ in range(n)]

metals = sorted(metals, key = lambda x : -x[1])
result = 0

for weight, price in metals:
  if w > weight:
      result += (weight * price)
      w -= weight
  else:
    result += (w * price)
    break

print(result)

  

에이 설마 이거겠어 했는데 맞았다.

정렬을 가격순으로 하려고 바로 리스트로 안만들고 append로 바꿔서 넣어줬는데

이부분이 시간초과에서 걸렸나보다 🤦‍♀️