Softeer - 금고털이 / Python

문제: https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=395 

Softeer

문제 설명

루팡은 배낭을 하나 메고 은행 금고에 들어왔다. 금고 안에는 값비싼 금, 은, 백금 등의 귀금속 덩어리가 잔뜩 들어있다. 배낭은 W ㎏까지 담을 수 있다. 각 금속의 무게와 무게당 가격이 주어졌을 때 배낭을 채울 수 있는 가장 값비싼 가격은 얼마인가?

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

입력 형식

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

입력은 다음 조건을 만족한다.
    1 ≤ N ≤ 106 인 정수
    1 ≤ W ≤ 104 인 정수
    1 ≤ Mi, Pi ≤ 104 인 정수

출력 형식

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

입력 예제

100 2
90 1
70 2

출력 예제

170

 

---

정답

# https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=395
import sys

input = sys.stdin.readline

w, n = map(int, input().split())

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

jewels.sort(key=lambda x: x[1], reverse=True)

answer = 0
for weight, price in jewels:
    if w > weight:
        answer += weight * price
        w -= weight
    else:
        answer += w * price
        break

print(answer)

 

---

풀이

 보석을 가방에 최대한 담되 가장 비싼 보석들을 위주로 가져가는 그리디 알고리즘 문제입니다.

 

 무게당 가격이 비싼 보석 순으로 가져가면 되며, 무게가 부족하면 톱으로 귀금속을 잘라서 가져갈 수 있으므로 넣을 수 있는 무게만큼 최대한 가져가면 됩니다. 보석을 가격순으로 정렬 후 반복하면서 (무게 * 무게 당 가격)만큼 answer를 증가시키고 무게가 모자라면 (남은 공간 * 해당 보석의 무게 당 가격)을 증가시키고 반복을 멈추면 해결할 수 있습니다.