[Softeer] 금고털이 파이썬

https://softeer.ai/practice/info.do?idx=1&eid=395 

Softeer

반응형

문제 정리

• 루팡은 배낭을 하나 메고 은행금고에 들어왔다.
• 금고 안에는 값비싼 금, 은, 백금 등의 귀금속 덩어리가 있다.
• 각 금속의 무게와 무게당 가격이 주어졌을 때 배낭을 채울 수 있는 가장 값비싼 가격을 구하라.
• 루팡은 전동톱을 가지고 있으며 귀금속은 톱으로 자르면 잘려진 부분의 무게 만큼 가치를 가진다.

해결방법

예제가 아래와 같이 주어진다.

100 2
90 1
70 2

• w = 100
• 보석의 개수 = 2
• 1번째 보석은 무게가 90이고 무게당 1값을 가진다.
• 2번째 보석은 무게가 70이고 무게당 2값을 가진다.

1. 가장 비싼 값을 만들어야 한다.
2. 입력받은 보석 무게와 무게당 가격을 배열에 넣는다.
3. 무게당 가격이 비싼 순으로 내림차순 정렬한다.
4. 무게 w와 무게당 가격을 비교하여 최대 값을 구한다.

여기서 무게당 가격이라는 것이

90 1이 주어지면, 이 보석은 1kg 당 1의 값을 가진다는 것이다.

마찬가지로 70 2는 1kg 당 2의 값을 가지는 것이다.

그렇기 때문에 무게당 가격이 높은 순으로 내림차순 정렬하는 것이다.

반응형

 

그림과 같이 보석의 최대 값을 구할 수 있다.

따라서 보석 100kg을 배낭에 담을 수 있는 최대 값은 170이 된다.

import sys
input = sys.stdin.readline

# 무게, 보석 개수
w, n = map(int, input().split())
graph = []

for i in range(n):
	# 무게, 무게당 가격
	m, p = map(int,input().split())
    graph.append([m,p])

graph = sorted(graph, key=lambda x: -x[1])

answer = 0
# 최대 값을 구하는 과정
for i in graph:
    weight = i[0]
    price = i[1]
    if w >= weight:
        answer += weight*price
        w-=weight
    else:
        answer += w*price
        break  

print(answer)