백준 2258번 - 정육점

문제

백준 2258번 - 정육점

아이디어

어떤 덩어리를 살 때 그 덩어리보다 싼 고기들은 덤으로 얻을 수 있다는 조건과 같은 가격은 더 무거운 무게의 덩어리가 최소 비용을 구하는 데 유리하다는 결론을 가지고 해결했다.

코드 구현 - 자바

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BJ_2258 {
    public static void main(String[] args) throws IOException {
        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());

        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken()); //무게
            arr[i][1] = Integer.parseInt(st.nextToken()); //가격
        }

        // 1
        Arrays.sort(arr, (a, b) -> {
            if (a[1] == b[1]) {
                return b[0] - a[0]; //가격이 같으면 무게 내림차순
            }
            return a[1] - b[1];
        });

        int totalWeight = 0;    //지금까지 은혜가 산 고기 무게
        int prevPrice = -1;     //이전 덩어리의 가격
        int cost = 0;           //고기를 구매하기 위한 비용
        int ans = -1;

        for (int[] a : arr) {
            int w = a[0]; //무게
            int p = a[1]; //가격

            // 2
            if (prevPrice == p) {
                cost += p;
            } else {
                cost = p; //포인트
            }
            prevPrice = p;
            totalWeight += w;

            // 3
            if (totalWeight >= m) {
                if (ans == -1 || cost < ans) {
                    ans = cost;
                }
            }
        }

        System.out.println(ans);
    }
}

1

• 덩어리 정보를 정렬한다.
• 기본적으로 가격을 기준으로 오름차순 정렬하며, 가격이 같으면 무게를 기준으로 내림차순 정렬한다.
• 가격이 같으면 무거운 덩어리가 먼저 계산되도록 하기 위해 내림차순 정렬한다.

2

• 정렬된 덩어리 정보를 순서대로 탐색하여 계산한다.
• 이전에 탐색했던 덩어리와 같은 가격일 때는 비용을 누적해준다. 왜냐하면 덤으로 얻을 수 있는 조건은 항상 싼 덩어리만 해당한다.
• 그러다가 가격이 같지 않을 때, 즉 이전 덩어리보다 비싼 가격일 때는 누적이 아닌 새롭게 초기화하는 것이 핵심이다.
• 이 한 덩어리의 가격으로 해당 가격 미만의 덩어리들을 모두 구매할 수 있다는 것을 의미한다.

3

• 은혜가 필요한 만큼 고기를 살 수 있을 때, 최소 비용을 갱신해준다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(NlogN)