백준 2258 - 정육점 (Python)

문제 정보

• https://www.acmicpc.net/problem/2258
• 그리디, 정렬

---

문제 정리

고기가 N덩어리 있다. 또한 어떤 고기를 샀을 때, 그 고기보다 싼 가격을 가지는 고기는 전부 덤으로 받을 수 있다. 고기 무게를 M 이상 사려고 할 때, 필요한 최소 비용을 구하는 문제이다.

---

풀이

일단 $N\leq100,000$이라대충 그리디거나 $O(N)$ DP거나 매개변수 탐색이거나 그 언저리 같았다.

매개 변수 탐색의 경우 고기를 가격순으로 정렬한 다음, 무게에 따라 최소 비용을 탐색해야 하는데, 가격에 따른 획득 무게가 선형이 아니기 때문에 불가능하다.
DP는 아무래도 힘들 것 같아서 그리디로 방향을 잡았다.

일단 구하고자 하는 것은 최소 비용이므로

• (고기 하나 + 해당 고기보다 싼 고기 전부 덤)
• (같은 가격 고기 여러 개 + 해당 고기보다 싼 고기 전부 덤)

이렇게 두 가지 케이스로 나누었다. 그 뒤 비용이 커지도록, 같은 비용이라면 무게가 줄어들도록 고기를 훑으면서, 현재 무게가 M 이상이 되는지 체크하는 방식으로 최소값을 구해줬다.

주의해야 할 점은 덤으로 받는 고기는 구매한 고기보다 싼 경우만 해당된다. 따라서 같은 가격의 고기를 여러 개 구매할 경우는 가격이 늘어나야 한다.

---

코드

# 백준 2258

import io

input = io.BufferedReader(io.FileIO(0), 1<<18).readline
INF = 10**10


def solve(N, M, cost):
    minCost = INF
    accW = 0
    for curC in sorted(cost.keys()):
        accC = 0
        
        # curC의 가격을 가지는 고기를 하나씩 추가로 구매
        for curW in sorted(cost[curC], reverse=True):
            accW += curW
            accC += curC
			
            # 무게가 M 이상일 경우
            if accW >= M:
                minCost = min(minCost, accC)

    return -1 if minCost == INF else minCost


def main():
    N, M = map(int, input().split())
    cost = dict()
    for _ in range(N):
        a, b = map(int, input().split())
        if b in cost:
            cost[b].append(a)
        else:
            cost[b] = [a]

    print(solve(N+1, M, cost))


main()