BOJ 2258 - 정육점

문제 링크

가격은 내림차순, 무게는 오름차순으로 정렬하고 순서대로 구매한다.
같은 가격이면 무거운 것 부터 사는것이 유리하기 때문에 무게는 오름차순으로 정렬해야 한다.

하나를 구매했을 때 구매한 가격보다 저렴한 고기는 그냥 가져갈 수 있지만
같은 가격인 고기를 여러개 사는 경우에는 같은 가격 개수만큼 가격을 지불해야 한다.

max_price와 count에 최대가격과 최대가격으로 구매한 수량을 담는다.
이때 여러개 샀을 경우에는 max_price보다 더 높은 가격과 max_price count를 비교해야 한다.
max_price보다 더 높은 가격이 max_price count보다 작을때 이미 무게는 다 채웠어도
그 가격의 고기를 사버리면 더 싼 가격으로 구매가 가능하다.

import sys


def read():
    return sys.stdin.readline().rstrip()


def get_next_price(info, price):
    for (p, w) in info:
        if p > price:
            return p
    return -1


def solution(info, required):
    info.sort()
    max_price = 0
    count = 0
    total_weight = 0
    for (price, weight) in info:
        weight *= -1
        if total_weight >= required:
            break
        # 구매
        total_weight += weight
        if price == max_price:
            count += 1
        else:
            max_price = price
            count = 1

    if total_weight < required:
        print(-1)
        return

    # max_price보다 비싼 가격이 있는지 확인
    next_price = get_next_price(info, max_price)
    if next_price != -1 and next_price < max_price*count:
        print(next_price)
    else:
        print(max_price*count)


info = []
N, M = map(int, read().split())
for _ in range(N):
    weight, cost = map(int, read().split())
    info.append((cost, -weight))

solution(info, M)