[Softeer] 금고털이 문제 (파이썬)

최초작성 : 3월 9일

📌 문제

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

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

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

Idea : 그리디 알고리즘을 사용하면 될 것 같다 :)

📌 제약조건

1 ≤ N ≤ 10^6인 정수
1 ≤ W ≤ 10^4인 정수
1 ≤ Mi, Pi ≤ 10^4인 정수

📌 입력형식

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

📌 출력형식

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

✏️ 입력예제1

100 2
90 1
70 2

✏️ 출력예제1

170

💁🏻‍ 코드

import sys
mat_list = []	#리스트 생성
price = 0	#최종 가격을 담을 변수
Bag_W, N = map(int, input().split())	#가방의 무게와, 금속의 종류 입력받기
for i in range(N):
    mat = list(map(int, input().split()))
    mat_list.append(mat)
mat_list.sort(key = lambda x : x[1], reverse=True)


for m, p in mat_list : 
    if Bag_W>=m :
        price += m*p
        Bag_W -=m
    else : 
        price += Bag_W * p
        break
print(price)

📌 코드 리뷰

for i in range(N):
    mat = list(map(int, input().split()))
    mat_list.append(mat)

• 금속의 종류만큼 금속의 무게와, 무게당 가격을 입력받는다.
• 이를 리스트 형식으로 [무게, 무게당 가격] 과 같이 만든 다음 mat_list 리스트에 추가한다.

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

• 무게당 가격이 높은 순으로 가방을 채워야 하기 때문에 sort() 함수를 이용한다.

for m, p in mat_list : 
    if Bag_W>=m :
        price += m*p
        Bag_W -=m
    else : 
        price += Bag_W * p
        break

• mat_list 리스트에 접근을 한다. 현재 mat_list는 무게당 가격 순으로 정렬되어 있다.
• 가방이 담을 수 있는 무게가 m보다 크거나 같을 때까지. 즉, 가방에 넣으려는 금속의 무게가 가방이 담을 수 있는 무게보다 작거나 같으면 if 문을 수행한다. if 문은 다음과 같다.

1. 무게 * 무게당 가격을 곱하여 가방에 넣는다
2. 가방이 담을 수 있는 무게에서 금속의 무게(Calculated)를 뺀다.

• 만약 가방이 담을 수 있는 무게가 금속의 무게보다 적다면, 금속은 자를 수 있기 때문에 그 다음 금속의 무게당 단위 * 가방이 담을 수 있는 무게를 곱하여 Price 가격에 더한다.