[소프티어] Lv2. 금고털이

2️⃣ 금고털이

https://softeer.ai/practice/6288

루팡은 배낭을 하나 메고 은행금고에 들어왔다. 금고 안에는 값비싼 금, 은, 백금 등의 귀금속 덩어리가 잔뜩 들어있다. 배낭은 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

💡아이디어

무게를 기준으로 sort를 해준다

그리고 배낭의 무게가 0이 될때까지

W에서 금속을 빼준다 ( 그 금속 무게 만큼 가격을 곱해서 저장 )

📝 풀이

import sys
from collections import deque

# 배당 무게 w, 귀금속 종류 n
w, n = map(int, input().split())
tmp = []

for i in range(n):
    tmp.append(list(map(int, input().split())))

#더 큰거 순서대로 정렬
tmp.sort(key = lambda x: x[1], reverse=True)

price = 0

for i in range(n):
    if w >= tmp[i][0]:
        w -= tmp[i][0]
        price += tmp[i][0] * tmp[i][1]
    else:
        price += w * tmp[i][1]
        break

print(price)