📚 2258 - 정육점

정육점

이해

문제에서 원하는 답안 고기를 구매하기 위해서 필요한 최소 비용을 계산한다.

(1) 고기 무게, 가격 입력 후 정렬하기

• 가격 오름차순, 무게 내림차순으로 정렬한다.

(2) 고기의 무게를 더해가면서 해당 고기가 이전에 탐색한 고기의 가격과 일치 여부를 확인한다.

• 만약, 이전 고기의 가격가 일치할 경우 해당 값을 더한다.

(3) 고기의 무게가 M 이상일 경우 결과 값을 갱신한다.

• 탐색한 고기 중 가격이 동일한 고기가 있을 경우 해당하는 값을 더한다.
• 고기의 무게가 M 이상이면서 최소의 가격으로 갱신한다.

소스

import sys  
  
read = sys.stdin.readline  
  
n, m = map(int, read().split())  
  
arr = []  
  
for _ in range(n):  
    weight, price = map(int, read().split())  
    arr.append((price, weight))  
  
arr.sort(key=lambda x: (x[0], -x[1]))  
  
ans = sys.maxsize  
same = 0  
weight = 0  
  
for i in range(n):  
  
    weight += arr[i][1]  

	# 이전과 같을 경우 same에 추가
    if i > 0 and arr[i][0] == arr[i - 1][0]:  
        same += arr[i][0]  
    else:  
        same = 0  
  
    # 현재 고기의 양이, 은혜가 필요한 고기의 양보다 많을 경우  
    if weight >= m:  
        # 가격을 비교한 후, 업데이트 한다.  
        ans = min(ans, arr[i][0] + same)  
  
answer = (ans if ans != sys.maxsize else -1)  
print(answer)

참고 : https://baby-ohgu.tistory.com/50