[정렬] Softeer level 2 금고털이 (Python 파이썬)

💡문제 링크

Softeer - 현대자동차그룹 SW인재확보플랫폼

💡문제 분석 요약

가방에 넣을 수 있는 최대 무게 w, 귀금속의 종류 n이 주어진다.

n개의 줄에 걸쳐서 귀금속의 총 개수 m과, 귀금속 한 개 당 가격 p가 나온다.

배낭에 담을 수 있는 가장 비싼 가격을 구하는 문제.

 

💡알고리즘 설계

1. 일단 귀금속의 개수와 가격 정보를 담은 2차원 배열 price를 만든다. p가 m보다 앞에 나오도록 한다.

     price = [[p1, m1], [p2, m2], ...]

2. 가격정보를 기준으로 price의 원소들을 내림차순 정렬한다.

3. 가장 값어치가 많이 나가는 귀금속을 가방에 담아서 그 가격을 answer 변수에 넣고, 남은 용량을 weight 변수에 넣는다. 

4. 그 다음 값어치가 많이 나가는 귀금속에 대해 3번의 과정을 반복한다.

5. weight가 0이 되기 전까지 3, 4의 과정을 반복한다.

6. 마지막에 answer값을 출력한다.

💡코드

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

# 초기값 세팅
weight = w
price = []
answer = 0

# 값 입력받기
for _ in range(n):
    m, p = map(int, input().split())
    price.append([p, m])

# 정렬하기
price.sort(key = lambda x: x[0], reverse = True)
# 반복문
i = 0
while weight > 0:
    answer += price[i][0] * min(weight, price[i][1])
    weight -= min(weight, price[i][1])
    i += 1

print(answer)

💡 느낀점 or 기억할정보

price.sort(key = lambda x: x[0], reverse = True)

이전에는 특정 기준을 바탕으로 배열 정렬하는 게 어려웠는데, 이제는 잘 하는 나 자신 칭찬해~

시간도 15분밖에 안 걸렸다.