[python] 소프티어 - 금고털이

소프티어 level 2 문제
https://softeer.ai/practice/info.do?idx=1&eid=395

8단 변속기문제보다는 생각을 해야하지만 쉬운 문제였다.


문제 조건에 무게당 금속의 가격이 최대 $10^4$까지 될 수 있으니 인덱스 10000까지의 리스트를 0으로 초기화하고 금속을 입력받으면 해당가격(인덱스)에 값으로 무게를 추가하였다.
그리고 뒤에서부터 배낭이 가득 찰 때까지 for문을 돌렸다.

# W kg 까지 담을 수 있는 배낭
# 금속의 무게와 무게당 가격이 주어졌을 때, 배낭을 채우는 가장 비싼 가격?

bag, n = map(int,input().split()) # 담을 수 있는 배낭의 무게, 금속의 종류
nowBag = 0
money = 0 # 배낭에 담을 수 있는 가장 비싼 가격
materials = [0] * 10001 # 금속의 무게당 가격을 인덱스, 무게를 값으로 하는 리스트 초기화
for i in range(n):
    weight, value = map(int,input().split()) # 금속의 무게, 무게당 가격
    materials[value] += weight

for i in range(10000, 0, -1):
    if materials[i] != 0:
        if nowBag + materials[i] <= bag:    # 해당 가격의 금속을 다 담을 수 있으면
            nowBag += materials[i] # 가방에 담고
            money = money + i * materials[i] # 돈 계산
        else:   # 금속을 다 못 담으면
            money = money + i * (bag-nowBag) # 담을 수 있을 만큼만 값을 더한다다
            break

print(money)

해설강의가 있었다.

https://softeer.ai/class/algotutor/detail.do?id=66
O(nlogn)의 풀이와 O(n)의 풀이가 있었는데
후자가 내 풀이의 로직이었다. 굿.