백준 - 2258번(정육점)

문제 출처: https://www.acmicpc.net/problem/2258

문제

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

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

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    private static class Meat implements Comparable<Meat> {

        int weight;
        int price;

        public Meat(int weight, int price) {
            this.weight = weight;
            this.price = price;
        }

        @Override
        public int compareTo(Meat o) {
            if (this.price == o.price) {
                return o.weight - this.weight;
            } else {
                return this.price - o.price;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
        int N = Integer.parseInt(tokenizer.nextToken()); // 고기 덩어리 수
        int M = Integer.parseInt(tokenizer.nextToken()); // 필요한 고기의 양

        List<Meat> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            tokenizer = new StringTokenizer(reader.readLine());
            list.add(new Meat(Integer.parseInt(tokenizer.nextToken()), Integer.parseInt(tokenizer.nextToken())));
        }

        Collections.sort(list);

        int totalWeight = list.get(0).weight;
        int totalPrice = list.get(0).price;

        int result = Integer.MAX_VALUE;

        boolean flag = false;

        for (int i = 1, size = list.size(); i < size; i++) {
            if (list.get(i).price == list.get(i - 1).price) { // 가격이 같은 경우
                totalPrice += list.get(i).price;
            } else { // 가격이 다른 경우
                totalPrice = list.get(i).price;
            }

            totalWeight += list.get(i).weight;

            if (totalWeight >= M) {
                flag = true;
                result = Math.min(result, totalPrice);
            }
        }

        System.out.println(flag ? result : -1);
    }

}

• 처음에는 도저히 생각이 나지 않았으나 계속 생각하다보니 실마리가 풀렸다.
• 핵심은 정렬에 있다. 먼저 가격 순으로 오름차순 정렬한다. 이는 최소 비용을 구하기 위함이다.
• 만약 가격이 같을 경우 무게 순으로 내림차순 정렬을 한다. 같은 가격일 때 더 무게가 많이 나가는 것을 택하는 것이 이득이기 때문이다.
• 리스트에 넣고 리스트를 정렬한 후 하나씩 순차 탐색해 나간다.
• 이때, 가격이 직전의 가격과 다른 경우(즉, 더 큰 경우) 전체 가격은 이 가격으로 된다. 앞전의 모든 것들은 덤으로 얻기 때문이다. 처음에 이 조건을 설정해 주지 않아 헤맸다.
• 직전의 가격과 같은 경우 누적 해준다.
• 만약, 고기의 가격이 기준 이상이 된 경우, 우선 값을 찾았으니 flag 값은 true를 준다.
• 기준 이상이 되었어도 최솟값을 찾기 위해 계속 진행한다.