[소프티어] 8단 변속기 - python (레벨 2)

https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=395 

Softeer

문제

루팡은 배낭을 하나 메고 은행금고에 들어왔다. 금고 안에는 값비싼 금, 은, 백금 등의 귀금속 덩어리가 잔뜩 들어있다. 배낭은 W ㎏까지 담을 수 있다. 각 금속의 무게와 무게당 가격이 주어졌을 때 배낭을 채울 수 있는 가장 값비싼 가격은 얼마인가?
루팡은 전동톱을 가지고 있으며 귀금속은 톱으로 자르면 잘려진 부분의 무게만큼 가치를 가진다.

 

입력형식

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

입력은 다음 조건을 만족한다.
    1 ≤ N ≤ 10^6 인 정수
    1 ≤ W ≤ 10^4 인 정수
    1 ≤ Mi, Pi ≤ 10^4 인 정수

 

출력형식

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

 

풀이

문제를 보았을때 알수있는 힌트

문제를 통해 최대로 가격이 비싼 무게 먼저 처리하면서 계산하면 되겠다는 생각을 할수있다. 문제는 그냥 for문을 통해 계산을 하면 시간 초과가 난다는 것이 문제이다.

이를 위해서 dp를 통해 문제를 해결하였다.

가격을 기준으로 무게를 다 더하여 dp에 보관하고

비싼 가격의 무게 만큼 w에서 빼가며 계산을 하면 시간초과 없이 문제를 해결할 수 있다.

 

import sys

input= sys.stdin.readline

w, n = map(int,input().split())

dp = {}
result=0
for i in range(n):
    m,p = map(int,input().split())
    if p in dp:
        dp[p]+=m
    else:
        dp[p]=m

for i in range(100001,-1,-1):
    if i in dp:
        if w>dp[i]:
            result=result+dp[i]*i
            w=w-dp[i]
        else:
            result=result+w*i
            break
print(result)

https://github.com/dydwkd486/coding_test/blob/main/softeer/장애물인식프로그램.py 

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리