[백준 - 2258][GOLD 4][해설 X] - 정육점 (JAVA)

 

문제 링크

---

https://www.acmicpc.net/problem/2258

 

문제

---

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

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

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

 

입력

---

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

 

출력

---

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

 

해결 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        PriorityQueue<Meat> pq = new PriorityQueue<>();
		
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());

            int weight = Integer.parseInt(st.nextToken());
            int price = Integer.parseInt(st.nextToken());

            pq.add(new Meat(price,weight));
        }

        int minPrice = -1; //최소 가격
        int weight = 0; //고기 총 무게
        int totalPrice = 0; //총 가격
        int beforePrice = 0; //이전 고기 가격

        while(!pq.isEmpty()){
            Meat curr = pq.poll();
           
            //고기 무게 더하기
            weight += curr.weight;

            //이전 고기 가격과 현재 고기 가격이 같다면 현재 고기 값을 추가로 지불.
            if(curr.price == beforePrice){
                totalPrice += curr.price;
            }
            //이전 고기 가격보다 현재 고기 가격이 비싸면 현재 고기 가격으로 모든 이전 고기를 살 수 있다.
            else{
                totalPrice = curr.price;
            }

            //원하는 고기 무게보다 많이 산 경우 최소 가격 찾기
            if(weight >= M){
                if(minPrice == -1){
                    minPrice = totalPrice;
                }else {
                    minPrice = Math.min(totalPrice, minPrice);
                }
            }

            beforePrice = curr.price;
        }

        System.out.println(minPrice);
    }
}

class Meat implements Comparable<Meat>{
    int price;
    int weight;

    public Meat(int price ,int weight){
        this.price = price;
        this.weight = weight;
    }
	
    //가격이 싸면서 무게가 무거운 순서로 정렬
    @Override
    public int compareTo(Meat o) {
        if(o.price == this.price){
            return o.weight - this.weight;
        }
        return this.price - o.price;
    }
}

 

 

실행 결과

---

 

팁

---

• 수를 비교할 때에는 작은 경우, 같은 경우, 큰 경우 3가지를 유의해야 한다.