소프티어 | 금고털이

소프티어 | 금고털이

문제

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



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



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

제약조건

1 ≤ N ≤ 106인 정수

1 ≤ W ≤ 104인 정수

1 ≤ Mi, Pi ≤ 104인 정수

입력

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

출력

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

내 풀이

import sys

# M = 가방의 무게 N = 귀금속 종류 수
M, N = map(int, input().split())
data = [[0]*2 for _ in range(N)]
result = 0

for i in range(N):
    # M1 = 금속의 무게 P1=  무게당 가격
    M1, P1 = map(int, input().split())
    data[i][0] = M1
    data[i][1] = P1

# 금속의 가격이 비싼 순으로 정렬
data.sort(key = lambda x : x[1], reverse = True)

for i in range(N):
    # 예) 100-70=30 인데 다음 금속의 무게가 90일 때, 문제가 생기므로 M의 범위를 잘 봐야함!
    if M >= data[i][0]:
        M -= data[i][0]
        result += data[i][0] * data[i][1]
    else:
        result += M * data[i][1]
        break

print(result)

처음 풀이를 할 때, 가격이 같을 때 정렬을 해줘야 한다고 착각을 해서 문제를 돌아돌아 풀었다,, 어제 푼 문제와 비슷해서 금방 해결한 재밌는 문제!