[Softeer] 금고털이

문제링크

---

금고털이

풀이과정

---

Greedy로 동전 뱉어주는 그런 느낌으로 풀면 된다. 뭔지 느낌 알지오 ?

일단 1그람당 무게가 높은 보석을 많이 챙기는게 돈을 많이 버는 방법이다.
그래서 jewelry에 받은 값을 1그람당 무게를 기준으로 정렬하자.(내림차순으로 해야한다!)

그리고나서 jewelry에 있는 아이들을 빼와서 베낭에 넣을 수 있는 무게인 W와 비교하고, 가방에 여유가 있을 경우 다 넣고, 없을 경우 잘라서 넣는 그런 방식이다 ~

📢 참고 : for문을 이용해서 입력 받을때는 input()보다 sys.stdin.readline()을 사용하자.

코드

---

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

jewelry = []
for i in range(N):
    jewelry.append(list(map(int, sys.stdin.readline().split())))

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

result = 0
for weight, price in jewelry:
    if weight < W:
        result += weight * price
        W -= weight
    else:
        result += W * price
        break

print(result) 

결과

---