[Softeer] python 금고털이

<본 블로그는 Softeer의 코딩테스트 문제를 참고해서 공부하며 작성하였습니다>

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

Softeer

 

⭐ 문제

언어별 시간/메모리

Python

3초

256MB

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

각 금속의 무게와 무게당 가격이 주어졌을 때 배낭을 채울 수 있는 가장 값비싼 가격은 얼마인가?
루팡은 전동톱을 가지고 있으며 귀금속은 톱으로 자르면 잘려진 부분의 무게만큼 가치를 가진다.

제약조건
1 ≤ N ≤ 106인 정수
1 ≤ W ≤ 104인 정수
1 ≤ Mi, Pi ≤ 104인 정수

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

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

입력예제1
100 290 170 2

출력예제1
170

 

✅ Code

# 금, 은, 백금 등의 귀금속 덩어리
# 배낭은 W ㎏까지 담을 수 있음
# 귀금속은 톱으로 자르면 잘려진 부분의 무게만큼 가치를 가짐

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

import sys

input = sys.stdin.readline

# 배낭 무게, 귀금속 종류
W, N = map(int, input().split())

table = []
for i in range(N):
    m, p = map(int, input().split())
    table.append((m, p))

# 가격 비싼 순서대로 -> [(70,2),(90,1)]
table.sort(key=lambda x: x[1], reverse=True)

answer = 0
# 금속의 무게 Mi와 무게당 가격
for m, p in table:
    if W > m:
        answer += m * p  # 보석 무게 * 가치
        W -= m
    else:
        answer += W * p  # 잘라낸 보석 무게 * 가치
        break
print(answer)