[Softeer] 금고털이

https://softeer.ai/practice/info.do?idx=1&eid=395&sw_prbl_sbms_sn=95234 

Softeer

문제

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

 

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

 

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

제약조건

1 ≤ N ≤ 106인 정수

1 ≤ W ≤ 104인 정수

1 ≤ Mi, Pi ≤ 104인 정수

입력형식

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

출력형식

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

입력예제1

100 2
90 1
70 2

출력예제1

170

 

---

문제접근

난이도가 2개다. 지금까지 풀었던 쉬운 문제도 다 난이도가 3개짜리였는데 왜 2개일까?

언뜻보면 냅색 알고리즘으로 풀어야할 것 같지만, 문제를 자세히 읽으면 난이도를 확 내려버리는 한 문장이 있다.

 

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

 

이 한 문장 때문에 그리디 문제가 된다. 단순히 가치가 제일 높은 귀금속부터 담아버리면 되기때문이다.

따라서 귀금속을 내림차순으로 정렬만 해놓으면 매우 문제가 단순해진다. 정렬을 해놓았다는 전제하에..

아래 단계를  따라가며 문제를 살펴보자

 

bag_w = 현재 가방에 남아있는 여유무게

m = 가방에 넣으려는 귀금속의 무게

p =  가방에 넣으려는 귀금속의 가치

 

라고 할때, 가방에 귀금속을 넣으려는 경우 두가지 경우가 발생한다.

 

if m > bag_ w

즉 현재 넣으려는 무게가 가방의 여유분 보다 무거운 경우이다. 이때 가치환산은 여유무게 * 귀금속의 가치 로 계산된다

왜냐? 전기톱으로 여유무게만큼 귀금속을 잘라버리면 되기때문이다.

그리고 이 경우는 가방의 무게가 가득 찬 것이기때문에 시행을 종료하면 된다. 

 

else ( m<=bag_w )

가방의 여유분이 더 남아있다면 가치환산은 현재 귀금속의 무게 * 귀금속의 가치 로 계산된다.

그리고 가방의 여유분 bag_w에서 현재 무게 m을 빼주어야한다. (가방에 귀금속을 넣었으므로)

 

이것만 이해하면 끝 ! 

 

---

import sys w , n = map(int,sys.stdin.readline().split()) # 전동톱이 있으므로 그리디 # 무게와 가격을 입력받자 g = [] for i in range(n):     m, p = map(int,sys.stdin.readline().split())     g.append((m,p)) sorted_g = sorted(g, key=lambda x:x[1], reverse = True) res_m = 0 res_p = 0   for m,p in sorted_g:     # 현재 금속의 무게 m, 가치 p     if m > w :         res_p += w * p         break          res_p += m * p     w -= m print(res_p)