BOJ_2258_정육점 (Java)

[Gold III] 정육점 - 2258

문제 링크

성능 요약

메모리: 43920 KB, 시간: 492 ms

분류

그리디 알고리즘, 정렬

제출 일자

2025년 5월 6일 15:16:41

문제 설명

은혜는 정육점에서 고기를 사려고 한다. 보통 정육점에서는 자신이 원하는 양을 이야기하면 그 양만큼의 고기를 팔지만, 은혜가 방문한 정육점에서는 세일 행사를 하고 있었기 때문에 N 덩어리의 고기를 이미 잘라놓고 판매하고 있었다.

각각의 덩어리들은 이미 정해져 있는 무게와 가격이 있는데, 어떤 덩어리를 샀을 때에는 그 덩어리보다 싼 고기들은 얼마든지 덤으로 얻을 수 있다(추가 비용의 지불 없이). 또한 각각의 고기들은 부위가 다를 수 있기 때문에 비용과 무게와의 관계가 서로 비례하는 관계가 아닐 수도 있다. 은혜는 이러한 점을 고려하지 않고, 어느 부위든지 자신이 원하는 양만 구매하면 되는 것으로 가정한다. 또한 만약 가격이 더 싸다면 은혜가 필요한 양보다 더 많은 고기를 살 수도 있다.

각 덩어리에 대한 정보가 주어졌을 때, 은혜가 원하는 양의 고기를 구매하기 위해 필요한 최소 비용을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 100,000), M(1 ≤ M ≤ 2,147,483,647)이 주어진다. N은 덩어리의 개수를 의미하고, M은 은혜가 필요한 고기의 양이다. 다음 N개의 줄에는 각 고기 덩어리의 무게와 가격을 나타내는 음 아닌 두 정수가 주어진다. 무게의 총 합과 가격의 총 합은 각각 2,147,483,647을 넘지 않는다.

출력

첫째 줄에 답을 출력한다. 불가능한 경우에는 -1을 출력한다.

문제 풀이

가격 기준으로 오름차순한다. 가격이 같으면 더해야하고 가격이 높아지면 그 가격으로도 아래가격 고기 다 살 수 있다. 그리고 고기 무게는 내림차순으로 무거운것부터 같은 가격으로 사면 좋으니 그렇게 정렬기준을 세운다.

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */

import java.io.*;
import java.util.*;

public class Main {
    class Meat implements Comparable<Meat>{
        int w, p;
        public Meat(int w, int p) {
            this.w = w;
            this.p = p;
        }

        @Override
        public int compareTo(Meat o) {
            if(this.p == o.p) return o.w - this.w;
            return this.p - o.p;
        }
    }
    static BufferedReader br;
    static BufferedWriter bw;
    static StringTokenizer st;
    static int N, M;
    static long res = Long.MAX_VALUE;
    static Meat[] meat;
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
//        br = new BufferedReader(new InputStreamReader(new FileInputStream("src/main/java/BOJ_2258_정육점/input.txt")));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        meat = new Meat[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            meat[i] = new Meat(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        Arrays.sort(meat);

        int prevP=0;
        int Wsum=0;
        int currP=0;
        for(Meat m : meat) {
            if(m.p > prevP) {
                prevP = m.p;
                currP = m.p;
            }
            else if(m.p == prevP) currP+=m.p;

            Wsum += m.w;

            if(Wsum >= M) res = Math.min(res, currP);
        }

        if (Wsum < M || res > 2_147_483_647) res = -1;

        System.out.println(res);

        br.close();
    }
}