[백준-파이썬] 2258: 정육점

백준 정육점 문제보러 가기!!

아이디어, 코드 설명 🌱

고기의 무게, 가격을 튜플로 받아서 리스트를 만든다.
가격이 낮은 순서대로, 가격이 같다면 무게가 큰 순서대로 정렬한다.
그리고 그 가격의 고기를 살 때, 얼마나 고기를 얻을 수 있는지(그 가격보다 낮은 고기는 덤으로 얻을 수 있다)를 dp에 저장한다.
고기의 무게, 가격이 저장된 리스트를 쭉~ 돌면서,
얻을 수 있는 고기의 양이 필요한 양 이상이면
그 가격을 비교해서(필요 고기 양이 충족되었을 때 가격이 같은 고기를 여러 개 샀을 수도 있고, 그것보다 가격이 비싼 고기를 하나 샀을 수도 있으니까!) 싼 가격을 min_price에 대입한다.
다 돌고 나서, min_price가 원래 초기화한 값 그대로라면(얻을 수 있는 고기 양이 필요양보다 적었다는 것이니까) -1를 출력한다. 그게 아니라면 그 값을 출력한다.

헷갈렸던 것 🌷

일단 맨 처음에는 가격이 같은 고기가 여러 개 있는 경우를 고려하지 않았다. 가격이 같은 고기를 여러 개 구매하는 경우 vs 가격이 더 비싼 고기를 하나 구매하는 경우를 비교해서 더 가격이 싼 것을 택해야 할 때가 있다.
예를 들면,
3 10
5 4
5 4
10 6
-> 무게 10 만큼 필요하다. 가격 4이고 무게 5짜리로 무게 10가 되려면, 두 개를 사야 한다. 가격 8이 필요한 것이다. 그런데 가격 6짜리를 사면! 가격 6으로 무게 20을 얻을 수 있다.

이걸 알기 전에는 고기 덩어리를 가격 기준 싼 것부터 정렬하기만 했다. 알고 난 후에는, 가격 싼 순으로 정렬하되, 가격이 같으면 무게가 큰 것을 먼저 정렬했다.
그리고 가격 같은 것을 여러 개 구매하는 경우, 몇 개나 구매했는지 갯수를 세줘서 비용이 얼마나 드는지 구했다. 또 가격 같은 것을 여러 개 구매하는 경우의 비용과 가격이 좀 더 비싼 것 하나 구매하는 경우의 비용을 비교하는 코드도 추가했다.

한편, 특정 가격의 고기 덩어리를 구매했을 때 얻을 수 있는 고기의 무게를 저장하는 리스트(아래 코드에서는 dp)를 만들어주지 않아서 시간 초과가 나왔다. 그러다 dp를 만들어주니 시간초과 문제를 해결되었는데, 틀렸습니다가 떴다.

그 이유는 같은 것을 여러 개 구매하는 경우에 그 갯수를 세는 변수를 초기화를 안해줬기 때문이었다. 내 생각에는 같은 것 여러 개를 구매해서 필요한 양 이상 구매하는 것 다음에는, 좀 더 비싼 비용으로 하나를 구매해서 필요한 양 이상으로 구매할 수 있을 것이다. 그것 두 개를 비교해주면 끝이겠지.! 이것만 생각했다.

여러 번 같은 것을 여러 개 구매하는 경우가 생길 수 있으니까, 갯수 세는 변수를 초기화해야 겠다고 생각했다. 여러 개 구매할 때 갯수 세는 변수도 초기화했는데.. 필요한 양 이상으로 구매를 하고, 하나만 구매할 때 변수를 초기화했다.

그랬더니

4 10
1 2
1 2
4 4
4 4

이런 경우에 틀렸다. (반례를 찾아준 친구! 고마워!)

갯수 세는 변수를 초기화하는 위치를 바꾸니, 정답이 되었다..!

최종 코드 🍒

import sys
input = sys.stdin.readline

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

for _ in range(N):
    meats.append(tuple(map(int,input().split())))

meats.sort(key=lambda x:(x[1],-x[0]))  # 가격 기준으로 싼 것부터 정렬 -> 가격 같으면 무게 큰 걸 먼저 정렬

dp = [0] * N # 해당 덩어리를 구매하면, 고기 양 얼마나 얻는지 

min_price = 2147483648
cnt = 1  # 가격 같은 것 여러 개 구매해야 할 때, 몇 개 구매해야 하는지 그 갯수

for i in range(len(meats)): # 가격 기준으로 쭉 돌아보기(싼 것부터)
    # 그 가격 이하의 고기 양 합이 필요한 양보다 많은지
    price = meats[i][1]

    if i != 0 and price == meats[i-1][1]:  # 가격 같은 것 여러 개 구매하는 경우
        cnt += 1
    else:
        cnt = 1

    dp[i] = dp[i-1] + meats[i][0]

    if dp[i] >= M:
        if price == meats[i-1][1]: # 가격 같은 것 여러 개 구매하는 경우
            min_price = min(price*cnt, min_price)

        else:  # 하나 구매하는 경우
            min_price = min(price, min_price)


if min_price == 2147483648: # 불가능한 경우
    print(-1)
else:
    print(min_price)