[Algorithm] Softeer 금고털이 - Lv.2 (Python)

[ Softeer 연습문제 - 금고털이 ]

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

• 문제명 : 금고털이
• 사용언어 : Python
• 사용 알고리즘 : 그리디 알고리즘

---

문제 설명

 

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

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

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

 

 

 

▼ 실행 코드 ▼

import sys
input = sys.stdin.readline

W, N = map(int, input().split())

jewelry = [list(map(int, input().split())) for _ in range(N)]
# 귀금속을 무게당 가격 기준으로 내림차순 정렬
jewelry.sort(key = lambda x : x[1], reverse = True)

result = 0

for m, p in jewelry:
  if W - m > 0:
    # 배낭에 귀금속을 통째로 넣을 수 있을 때
    W -= m
    result += (m*p)
  else:
    # 배낭에 귀금속을 일부만 넣을 수 있을 때
    result += (W*p)
    break

print(result)

 

▼ 실행결과 ▼ 

 

 

---

학습 회고

: 주어진 배낭의 용량에 따라 귀금속을 선택하여 배낭에 넣어 최대 가치를 계산하는 그리디(Greedy) 알고리즘을 사용하여 구현하였다. 귀금속을 통째로 넣을 수 있을 때와 일부만 넣을 수 있을 때로 조건을 나누어서 조건에 따라 배낭에 담을 수 있는 가장 비싼 가격을 출력했다.