[백준] 2258 정육점

문제링크 : https://www.acmicpc.net/problem/2258

2258번: 정육점

 

코드

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

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

        int[][] cost = new int[n][2];

        for (int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            int mass = Integer.parseInt(st.nextToken());
            int price = Integer.parseInt(st.nextToken());
            cost[i] = new int[]{mass, price};
        }

        Arrays.sort(cost, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                // 0 : 무게, 1 : 가격
                // 가격 오름차순 정렬
                // 같은 가격이라면, 무게 내림차순
                // 가격은 적으면서 무게는 큰 고기를 고르기 위함

                // 가격을 비교하여 오름차순으로 정렬
                if (Integer.compare(o1[1], o2[1]) == 0) {
                    // 가격이 같은경우, 무게를 비교하여 내림차순으로 정렬
                    return Integer.compare(o2[0], o1[0]);
                }
                // 가격이 다른 경우, 가격을 기준으로 오름차순 정렬
                return Integer.compare(o1[1], o2[1]);
            }
        });

        // 특정 고기까지 구입했을 때 지불해야 하는 돈
        int totalPrice = -1;
        // 특정 고기까지 구입했을 때의 총 그램 수
        int totalGram = 0;
        // 목표 무게까지 살 수 있는지 판단
        int ans = Integer.MAX_VALUE;
        boolean isPossible = false;

        for (int i=0; i<n; i++){
            // 목표 무게를 넘었더라도 가격이 더 싸면 사기 때문에
            // 모든 고기를 다 산다고 가정해야 함

            // 고기 구입
            totalGram += cost[i][0];

            // 이전과 같은 가격일 경우
            if (i>0 && cost[i-1][1] == cost[i][1]){
                // = 돈 주고 사야함
                totalPrice += cost[i][1];
            } else {
                // 이전과 가격이 다르면
                // 가격은 오름차순 정렬 되어 있기 때문에
                // 해당 가격 이전의 고기들(=싼 고기) 공짜로 구입 가능
                // = 총 금액 갱신
                totalPrice = cost[i][1];
            }

            if (totalGram >= m){
                // 목표 무게 달성 시,
                isPossible = true;
                // 목표 무게를 넘었더라도 가격이 더 싼 것을 구매
                ans = Math.min(ans, totalPrice);
            }
        }

        bw.write(isPossible ? ans + "\n" : -1 + "\n" );
        bw.flush();
        bw.close();
    }
}

 

풀이

1. 구매한 가격보다 저렴한 가격의 고기는 공짜로 얻음

- 같은 가격이면서 무게는 큰 고기를 구입해야 함

- 따라서, 배열의 정렬을 (1) 가격 : 오름차순 / (2) 무게 : 내림차순 으로 해줘야함.

 

2. 원하는 목표 양을 구매하지 않았는데, 같은 가격의 고기가 나오면

- 구매가 보다 저렴한 고기만 얻을 수 있기 때문에 구입하려면 돈을 지불.

 

3. 가격이 더 저렴할 때 필요한 양보다 많이 살 수 있는 경우도 있을 수 있음

- 목표 양을 채웠어도 더 저렴한 고기가 나타날 수 있기 때문에 계속 구매 진행