[자바] 백준 2258 - 정육점 (java)

목차

문제 : boj2258

 

 

필요 알고리즘

• 그리디 알고리즘, 정렬
  
  • 그리디 알고리즘으로 풀 수 있는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  어떤게 이득일지 직관적으로 한번 생각해보자. 뭐 당연히 싸고 무게 높은 고기일수록 이득이다. 그럼 싼게 더 중요할까 무게 높은게 더 중요할까?

 

  이 문제의 경우엔 둘 중 하나를 선택하기가 어려운데, 어떠한 덩어리를 샀을 때 그 덩어리보다 싼 고기는 무료로 구매가 가능하기 때문이다. 이것때문에 상당히 꼬일 수 있다. 어떤 규칙으로 고기들을 살펴보는게 이득일지 잘 생각해봐야 한다.

 

A. 가격 오름차순으로 보는게 좋다.

  가격 오름차순으로 고기들을 본다고 해보자. 이 경우 나중에 본 고기는 가격이 더 높은 고기이고, 그 이전 고기들의 무게를 전부 합쳐버릴 수 있다. 우선 고기의 가격이 모두 다른 경우를 생각해보자.

5 9
1 1
1 2
1 3
1 4
9 5

 

  가격 오름차순대로 본다면 순서대로 다음과 같이 무게를 얻을 수 있다.

1. 무게 1에 가격 1

2. 무게 2에 가격 2

3. 무게 3에 가격 3

4. 무게 4에 가격 4

5. 무게 13에 가격 5

 

  애초에 무게 9에 가격5인걸 바로 골라도 상관없긴했다. 하지만, '필요한 양보다 더 많은 고기를 살 수도 있다' 라는 조건이 있으므로 굳이 무게를 줄일 생각은 하지 않아도 된다. 가격 오름차순으로 보면 항상 최선의 선택을 할 수 있다.

 

 

B. 가격이 동일한 것 끼리는 무게 내림차순으로 보는게 좋다.

  가격이 같은 것들을 보고 있는 동안엔, 더 높은 가격의 고기를 구매하기 전까지는 가격을 전부 지불해야 한다! 그렇다면 무게가 높은 순서대로 보는게(무게 내림차순) 더 이득이다.

 

  예를들어 다음 예시를 보자.

5 15
3 1
2 2
2 2
2 2
10 2

 

  'A'에서 얘기했듯이 가격 오름차순으로 볼꺼다. 다만 동일한 가격에 대해 정렬을 하지 않았다고 생각해보자. 즉, 위에 입력으로 들어온 순서대로 확인해보자.

1. 무게 3에 가격 1

2. 무게 5에 가격 2

3. 무게 7에 가격 4

4. 무게 9에 가격 6

5. 무게 19에 가격 8

-> 총 8의 가격이 필요하다.

 

  그럼 이번엔 동일한 가격에 대해서는 무게를 내림차순으로 봐보자.

1. 무게 3에 가격 1

2. 무게 13에 가격 2

3. 무게 15에 가격 4

-> 총 4의 가격이 필요하다.

 

  'A'와 'B'로 정렬을 어떻게 할지 정해졌다. 이하 코드는 ORDER BY price ASC, weight DESC로 정렬하는 코드이다.

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(final Meat o) {
        if (this.price == o.price)
            return o.weight - this.weight;
        return this.price - o.price;
    }
}

 

 

C. 원하는 무게가 채워졌다고 거기서 멈추면 안된다.

  이건 바로 예시를 보자.

4 15
3 1
2 2
10 2
20 3

 

  위에서 말한대로 진행해보면 다음과 같이 진행된다.

1. 무게 3에 가격 1

2. 무게 13에 가격 2

3. 무게 15에 가격 4

4. 무게 35에 가격 3

 

  즉, 원하는 무게가 채워졌다고 거기서 끝내면 '4'의 가격이지만, 더 진행해보면 '3'의 가격으로 가능하다. 따라서 끝까지 진행을 해봐야 답을 알 수 있다.

for (Meat cur : arr) {
    weightSum += cur.weight;	// 무게는 계속 더해지면 된다. 무게는 신경쓰지 말자.

    if (bfPrice != cur.price) {	// 이전에 봤던 가격과 현재 가격이 다른건 가격이 증가했다는 의미
        priceSum = bfPrice = cur.price;	// 얘기했듯이 이 경우 가격이 초기화된다. ('A' 내용)
    } else {
        priceSum += cur.price;	// 가격이 동일한 동안엔 가격을 계속 내줘야한다('B' 내용)
    }

    if (weightSum >= m) {	// 목표치인 M을 넘긴 이후에는 계속해서
        min = Math.min(min, priceSum);	// 최소 가격을 확인해야한다 ('C' 내용)
    }
}

 

 

코드 : github

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

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        Meat[] arr = new Meat[n];
        int total = 0;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int weight = Integer.parseInt(st.nextToken());
            int price = Integer.parseInt(st.nextToken());
            arr[i] = new Meat(weight, price);
            total += weight;
        }
        if (total < m) {
            System.out.println(-1);
            return;
        }

        Arrays.sort(arr);

        int bfPrice = 0;
        int weightSum = 0;
        int priceSum = 0;
        int min = Integer.MAX_VALUE;
        for (Meat cur : arr) {
            weightSum += cur.weight;

            if (bfPrice != cur.price) {
                priceSum = bfPrice = cur.price;
            } else {
                priceSum += cur.price;
            }

            if (weightSum >= m) {
                min = Math.min(min, priceSum);
            }
        }

        System.out.println(min);
    }
}

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(final Meat o) {
        if (this.price == o.price)
            return o.weight - this.weight;
        return this.price - o.price;
    }
}