[Python3] 금고털이 - Softeer(LEVEL2)

문제

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

 

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

 

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

제약조건

1 ≤ N ≤ 106인 정수

1 ≤ W ≤ 104인 정수

1 ≤ Mi, Pi ≤ 104인 정수

입력형식

첫 번째 줄에 배낭의 무게 W와 귀금속의 종류 N이 주어진다. i + 1 (1 ≤ i ≤ N)번째 줄에는 i번째 금속의 무게 Mi와 무게당 가격 Pi가 주어진다.

출력형식

첫 번째 줄에 배낭에 담을 수 있는 가장 비싼 가격을 출력하라.

입력예제1

1002
901
702

출력예제1

170

 

 

import sys
#입력 개수
global bag
bag, N = map(int, input().split()) #sys.stdin.readline() bag는 계속 update
metal =[] #입력받은값들 리스트로,
for i in range(N):
    met, price = map(int, input().split())
    metal.append([met,price])

metal.sort(key = lambda x : x[1], reverse=True) #무게당 가격 내림차순 정렬 -> 비싼걸걸 최대한 많이 담으면 되므로


def check(i, pr):
    global bag
    if metal[i][0]<=bag:
        bag-=metal[i][0]
        pr += metal[i][1] * metal[i][0]
    else:
        #누적무게를 보내줘야함 -> global 처리
        pr += metal[i][1] * bag
        bag = 0
    
    return pr


pr =  0

for i in range(0, len(metal)):#while? for?어떻게 저 무게까지로 제한하지 ->100에서 남은은 무게를를 재기기.
    
    pr = check(i, pr)
    if bag<=0:
        break

print(pr) #최종 업데이트된 pr 출력

 

고민거리

중간에 왜 240이라는 출력값이 나왔는지 모르겠음 -> check함수 입력 인자값으로 bag(이전엔 누적 무게값인 acweight이었는데, 처음 무게에서 greedy로 빠져나간걸 반영해줌) 줬던걸 global로 바꾸니 해결됨