[python] 백준 2258 정육점

https://www.acmicpc.net/problem/2258

2258번: 정육점

 

문제 해결

• 특이한 것이 어떤 고기의 가격보다 싼 고기들이 공짜라는 점이다.
• 그러므로 가격이 싼 것부더 정렬을 하여 for 문을 통해 가격을 정한 다음 그 이전의 고기의 무게들을 더해 원하는 고기량보다 큰 것들을 종합하여 가장 작은 가격이 정답이 된다.
• 가격 오름차순으로 정렬했기 때문에 가능한 답이 나오면 그것이 정답이라고 생각할 수 있지만 이전과 동일한 가격이여서 앞에 것을 공짜로 못얻어 비싸지는 경우가 있다. ex) 4, 4, 6 .. 그러면 4원 한번 계산 후 질량이 모자라 다음 4원 계산 때 넘었는데 이 때 가격은 8원으로 뒤에 6원보다 비싸다.

 

CODE

import sys
INF = sys.maxsize


n, m = map(int, input().split())
memo = []
total = 0
dp = [0]*(n+1)
for _ in range(n):
    a, b = map(int, input().split())
    memo.append((a,b))
    total += a
if total < m:
    print(-1)
else:
    memo.sort(key=lambda x:(x[1],-x[0]) ) #가격은 싼것부터, 무게는 큰 것 부터
    min_price = INF
    cnt = 1
    for i in range(len(memo)):
        price = memo[i][1] # 가격을 더하지 않는 이유는 가격이 비싸면 그보다 더 싼 것들은 공짜이기 때문
        if i != 0 and price == memo[i-1][1]: # 이전과 가격이 같으면 이전 것은 공짜가 아니기 때문에... cnt를 +1 하여 사야할 개수를 증가시킨다.
            cnt += 1
        else:
            cnt = 1
        dp[i] = dp[i-1] + memo[i][0] # 앞의 고기는 공짜이기 때문에 질량을 더한다.
        if dp[i] >=m: # 못넘으면 의미 없음
            min_price = min(price*cnt, min_price)
    print(min_price)