[백준 2258] 정육점

문제
정육점에서 N개의 덩어리 중 무게 M만큼 사려고한다.
정육점은 이미 무게와 가격이 정해져있는데 어떤 덩어리를 샀을 때 그 덩어리보다 싼 고기들은 추가지불없이 얻을 수 있다.
정확히 M만큼의 무게가 되지 않는다면 그 이상을 살 수도 있다.
이때 M만큼의 고기를 사기위해 필요한 최소비용을 구하라

입력
첫째 줄에 N과 M이 주어진다.
이후 N개의 줄에 고기의 무게와 가격이 입력된다.

출력
최소비용을 출력하고 만약 구할 수 없다면 -1을 출력한다.

---

접근

가장 적은 비용으로 M의 고기를 사야한다. 고기의 무게와 가격이 입력되었을 때 가격은 오름차순으로 정렬, 무게는 내림차순으로 정렬한다. 즉 가장 싼 가격을 갖는 고기의 무게를 더해나간다. 왜냐하면 비싼 가격은 그 미만의 가격을 갖는 고기를 꽁짜로 얻을 수 있기 때문에 싼 가격의 고기를 더하다가 무게가 M 이상일 때 그 때의 가격을 비교해보면된다.

 

이때 주의해야할 사항은 같은 가격을 갖고있지만 무게가 다른 고기들이다. 기본적으로 같은 가격일 때는 무게가 더 많은 나가는 고기를 먼저 더하게된다. 문제에서 싼가격에 대해서만 꽁짜로 가져갈 수 있다고 했기 때문에 같은 가격일 때는 무게를 더할 때 추가적으로 해당 가격을 더해줘야한다.

 

구현

먼저 고기의 무게와 가격에 대해 입력을 받는다.

지금은 문제에서 주어진대로 무게-가격 순으로 입력을 받았는데 나중에 정렬을 할 때 가격을 먼저 오름차순 정렬하게되는데 애초에 리스트에 넣을 때 가격-무게로 넣어주면 시간을 줄일 수 있다.

N, M = map(int, input().split())
meat_list = [list(map(int, input().split())) for _ in range(N)]

 

입력받은 고기를 가격은 오름차순, 무게는 내림차순으로 정렬한다.

여기서 .sort()보다 sorted()가 좀 더 시간이 절약되었다.

meat_list = sorted(meat_list, key=lambda x:(x[1], -x[0]))

 

그 다음 해를 구하기 위한 solve함수이다.

처음에 입력받은 고기의 무게를 모두 더해서 M이상을 얻을 수 있는지 판별한다.

없다면 바로 -1을 출력한다.

 

이후에 최소비용을 구하기위한 부분이 실행된다.

계속해서 무게를 더하다가 무게가 M이상이 되면 최솟값 비교를 실행한다.

이때 현재 가격이 이전의 가격과 같다면 동일한 가격끼리 더해주어 same_price에 저장한다.

나중에 최솟값 비교를 할 때 현재 가격과 동일한 가격이있으면 이 가격도 더해줘서 비교를 해준다.

이 부분 실행후 최소비용이 담긴 answer을 반환한다.

def solve():
    total = 0
    for idx in range(N):
        total += meat_list[idx][0]
    if total < M:
        return -1

    answer = sys.maxsize
    weight = 0
    same_price = 0
    for i in range(N):
        weight += meat_list[i][0]
        if i>=1 and meat_list[i][1] == meat_list[i-1][1]:
            same_price += meat_list[i][1]
        else:
            same_price = 0

        if weight >= M:
            answer = min(answer, meat_list[i][1]+same_price)
    return answer

---

전체 코드

import sys
input = sys.stdin.readline

def solve():
    total = 0
    for idx in range(N):
        total += meat_list[idx][0]
    if total < M:
        return -1

    answer = sys.maxsize
    weight = 0
    same_price = 0
    for i in range(N):
        weight += meat_list[i][0]
        if i>=1 and meat_list[i][1] == meat_list[i-1][1]:
            same_price += meat_list[i][1]
        else:
            same_price = 0

        if weight >= M:
            answer = min(answer, meat_list[i][1]+same_price)
    return answer

N, M = map(int, input().split())
meat_list = [list(map(int, input().split())) for _ in range(N)]

meat_list = sorted(meat_list, key=lambda x:(x[1], -x[0]))
#meat_list.sort(key=lambda x: (x[0], -x[1]))

result = solve()
print(result)

 

느낀점

그리디는 매 선택마다 최적의 선택을 하는 알고리즘이라는 개념만 알고 실제로 느낌을 받지 못하였다. 계속해서 그리디 알고리즘과 관련된 문제를 풀면서 그리디 알고리즘을 완벽하게 이해해야겠다. 

이 문제에서는 M이상의 고기를 선택하기 전까지 낮은 가격의 고기를 선택하고 가격이 같다면 무게가 더 많이나가는 고기를 선택하는 것이 기본 틀이며 이를 쉽게하기 위해 정렬을 해주었다.