[백준 2258번] 정육점 (Python) (최댓값을 사용할 때, 1e9보다 sys.maxsize가 더 안전하다 !)

> 파이썬, 그리디 알고리즘, 정렬

 

 

 

 

 

 

📖 문제 : 정육점 (Python)

 

 

은혜는 정육점에서 고기를 사려고 한다. 보통 정육점에서는 자신이 원하는 양을 이야기하면 그 양만큼의 고기를 팔지만, 은혜가 방문한 정육점에서는 세일 행사를 하고 있었기 때문에 N 덩어리의 고기를 이미 잘라놓고 판매하고 있었다.

각각의 덩어리들은 이미 정해져 있는 무게와 가격이 있는데, 어떤 덩어리를 샀을 때에는 그 덩어리보다 싼 고기들은 얼마든지 덤으로 얻을 수 있다(추가 비용의 지불 없이). 또한 각각의 고기들은 부위가 다를 수 있기 때문에 비용과 무게와의 관계가 서로 비례하는 관계가 아닐 수도 있다. 은혜는 이러한 점을 고려하지 않고, 어느 부위든지 자신이 원하는 양만 구매하면 되는 것으로 가정한다. 또한 만약 가격이 더 싸다면 은혜가 필요한 양보다 더 많은 고기를 살 수도 있다.

각 덩어리에 대한 정보가 주어졌을 때, 은혜가 원하는 양의 고기를 구매하기 위해 필요한 최소 비용을 계산하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 100,000), M(1 ≤ M ≤ 2,147,483,647)이 주어진다. N은 덩어리의 개수를 의미하고, M은 은혜가 필요한 고기의 양이다. 다음 N개의 줄에는 각 고기 덩어리의 무게와 가격을 나타내는 음 아닌 두 정수가 주어진다. 무게의 총 합과 가격의 총 합은 각각 2,147,483,647을 넘지 않는다.

 

 

출력

첫째 줄에 답을 출력한다. 불가능한 경우에는 -1을 출력한다.

 

 

예제 입력 1 

4 9
1 2
2 4
3 6
4 8

 

예제 출력 1 

8

 

힌트

무게가 4, 가격이 8인 고기를 하나 사면 나머지 고기를 모두 덤으로 얻을 수 있다. 이때 구매한 고기는 10kg이 되어 9kg 이상이 된다.

 

 

 

 

내 코드

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
beaf = []

for _ in range(N):
    weight, price = map(int, input().split())
    beaf.append((price, weight))

beaf.sort(key=lambda x: (x[0], -x[1]))

weight_sum = 0
same_price = 0
result = sys.maxsize

for i in range(N):
    weight_sum += beaf[i][1]

    if i > 0 and beaf[i][0] == beaf[i - 1][0]:
        same_price += beaf[i][0]
    else:
        same_price = 0

    if weight_sum >= M:
        result = min(result, beaf[i][0] + same_price)

if result != sys.maxsize:
    print(result)
else:
    print(-1)

 

 

 

 

Point ! ⭐️ 

• 이 문제의 포인트는 !
  사려고 하는 덩어리보다 싼 동어리는 꽁짜로 얻을 수 있다는 점이고,
  그렇기 때문에 같은 가격의 덩어리가 살 수 있는 덩어리들에 속해 있다면, 그 같은 가격의 덩어리는 꽁짜가 아니기 때문에 그 가격도 더해줘야 한다는 것입니다.

 

• 그리고 이 문제를 풀면서 알았는데, 최댓값을 사용할 때 '1e9' 를 배워서 사용하려 했는데, 이 값 때문에 채점하는데 40%에서 계속 틀리더라구요 !
  
  찾아보니 sys.maxsize를 사용하는 것이 더 안전하다는 거 !!!
  "sys.maxsize를 이용하는 이유는 들어가는 값이 1e9처럼 값을 정해놓으면 그것보다 큰 값이 들어가는 경우가 있기때문에 더 안전함." 이라고 합니다..
  
  이거때문에,, 왜 틀린지도 모르고 계속 틀렸숴 ,,  😭

 

 

 

 

 

 

 

백준

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

2258번: 정육점