[소프티어] 금고털이

https://softeer.ai/practice/6288

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

 

접근

---

• 무게와 무게당 가격이 주어졌을 때, 배낭을 채울 수 있는 가장 비싼 가격은 얼마인가?
  → 무게당 가격을 기준으로 내림차순 정렬
• 귀금속을 톱으로 자를 경우, 잘려진 부분의 무게만큼 가치를 가진다
  → 남은 배낭 무게보다 귀금속의 무게가 작은 경우, 자르지 않는다 / 남은 배낭 무게보다 귀금속의 무게가 큰 경우, 자른다

 

코드

---

import sys

w, n = list(map(int, sys.stdin.readline().split()))

gold = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]
gold.sort(key=lambda x:x[1], reverse=True)

answer = 0
for (weight, value) in gold:
    if weight < w:
        w -= weight
        answer += weight*value
    else:
        answer += w*value
        break

print(answer)