백준 2258 정육점 python

그리디하게 접근하여 해결할 수 있는 문제.
문제 레벨이 높지 않아서 그런지 그리디 문제는 너무 깊게 생각할 필요는 없는거 같다.

📜 문제 바로 가기 : 정육점

제출코드

파이썬

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

arr = [0] * N

for i in range(N):
    w, c = map(int, input().split())
    arr[i] = (w, c)

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

weight = 0
MAXcost, total = 0, 0
for i in range(N):
    w, c = arr[i]
    if weight < M :
        weight += w
        if MAXcost == c :
            total += c
        else:
            MAXcost = c
            total = c
    
    elif MAXcost == c:
        continue
    
    elif total > c :
        total = c
        break

    else:
        break

if weight < M:
    print(-1)
else:
    print(total)

---

접근방법

정육점의 고기의 무게와 가격값을 가격은 낮은 순서대로 가격이 같다면 무게는 높은 순서로 정렬한다.
그 후 가장 싼 고기부터 하나씩 구매해보는 방법이다.
배열을 한 번만 탐색하므로 O(N), N = 10만 시간은 충분하다.

가격은 가장 비싼 고기만 값을 받으므로 고기 가격이 같다면 내야할 돈(total)은 계속 늘어날것이다.

생각해야 될 점은 고기를 사다가 원하는 목표치 total <= M 에 도달했다면 이제 고기를 더 사더라도 더 싸게 구매가능한지만 확인하면 된다.

가격이 더 싸지는 경우는 현재 최고가(MAXcost) 보다 좀 더 비싼 고기의 가격이 현재 내야될 돈 보다 작으면 되겠다.(total < c)