백준 2258 (정육점) - java

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

2258번: 정육점

문제

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

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

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

 

유형 : 정렬 + 그리디

 

접근 방식

• 우선 해당 문제에서 중요한 점은 정렬 기준을 정하는 것이다. (가격이 높다면 낮은 가격의 고기들은 공짜!) 이기 떄문에 가격을 오름차순으로 하고 무게의 내림차순을 2번째 정렬 기준으로 한다.
• 위 문제에서 고려해야 할 점은 단 1가지 경우이다.
• (1,5) , (1,5), (2,6) 의 경우에 2이상의 무게를 만족해야 한다면 답은 10이 아니라 6이어야 한다.
  • 즉 같은 가격의 경우를 고려해야 한다.
  • 가격이 같다면 이전 가격에서 더해줘야 한다.
  • 가격이 다르다면 더 큰 가격으로 설정한다.
• 기준 무게를 달성한 경우 가격을 갱신해준다.

전체 코드

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

public class Main {
    static int n = 0;
    static int m = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        Node[] arr = new Node[n];

        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine(), " ");
            int s = Integer.parseInt(st.nextToken());
            int p = Integer.parseInt(st.nextToken());

            arr[i] = new Node(s,p);
        }

        Arrays.sort(arr,(x,y) -> {
            if(x.p == y.p)
                return y.s - x.s;

            return
                x.p - y.p;});
        // 가격으로 오름 차순 , 무게로 내림 차순

        int tmp = 0; // size
        int price = 0; // price
        int past = 0;

        int result = Integer.MAX_VALUE;
        for(int i=0;i<n;i++){
            tmp += arr[i].s;

            if(arr[past].p == arr[i].p){
                price += arr[i].p;
                past = i;
            }

            else if(arr[past].p < arr[i].p){
                price = arr[i].p;
                past = i;
            }

            if(tmp >= m){
                result = Math.min(result,price);
            }
        }

        if(tmp < m){
            System.out.println(-1);
        }
        else
            System.out.println(result);

        br.close();
    }
}
class Node{
    int s;
    int p;

    Node(int s,int p){
        this.s = s;
        this.p = p;
    }
}