Softeer - 금고털이 (Python)

Lv2, ⭐⭐

풀이

분할가능 배낭문제
Greedy의 대표적 문제이다.
값 기준 내림차순 정렬을 통해 해결할 수 있다.
처음에 딕셔너리로 해결하다가 무게가 중복될 수 있다는 점을 인지 못해 애를 먹었다.

from sys import stdin

w, n = map(int, stdin.readline().split())
jewels = []
for i in range(n):
    M, P = map(int, stdin.readline().split())
    jewels.append([P, M])

sorted_jewels = sorted(jewels, key = lambda x : (-x[0]))

res = 0

for v, m in sorted_jewels:
    if m <= w:
        res += (v * m)
        w -= m
    else:
        res += (v * w)
        break

print(res)