[백준/2258] 정육점 (Java)

Question

• 문제 링크 : https://www.acmicpc.net/problem/2258
• 분류 : Greedy
• 풀이 시간 : 2시간

문제 해설

1. N : 정육점에서 파는 고기 덩어리 개수
2. M : 은혜가 필요한 고기의 양
3. 특정 덩어리를 구입하면, 그것보다 싼 고기들은 공짜로 얻음
4. 부위 상관 없이 필요한 양 만큼의 고기만 사면 됨
5. 가격이 더 싸면 필요한 양보다 더 많이 살 수 있음

Solution

풀이 접근 방법

시행착오를 많이 격은 문제다

간단하게 무게로 오름차순 정렬 후 무게를 더하면서 목표한 무게 이상이 되면 그에 해당하는 가격이 정답인줄 알았는데 아니였다..

이 때부터 헬게이트 오픈!

1. 구입한 고기보다 싼 고기는 공짜로 얻음
   • 같은 가격이면서 무게는 큰 고기를 구입해야한다.
   • 정렬 : 가격 오름차순 -> 무게 내림차순
   • 배열 정렬 : Comparator 사용
2. 그러면 원하는 목표 양보다 사지 않았는데 같은 가격의 고기가 나타나면?
   • 싼 고기만 공짜로 얻을 수 있기 때문에 구입하려면 돈 지불해야 함
   • 지불해야하는 금액에 돈 더해줌
3. 가격이 더 사면 필요한 양보다 많이 살 수 있음
   • 목표 양을 채웠어도 더 싼 고기가 나타날 수 있기 때문에 계속 사봐야 함

정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Comparator;

public class Main_2258 {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    String[] info = br.readLine().split(" ");

    int N = Integer.valueOf(info[0]);
    int M = Integer.valueOf(info[1]);
    int[][] price = new int[N][2];

    for (int i = 0; i < price.length; i++) {
      info = br.readLine().split(" ");
      price[i] = new int[] { Integer.valueOf(info[0]), Integer.valueOf(info[1]) };
    }

    Arrays.sort(price, 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 answer = Integer.MAX_VALUE;
    boolean isPossible = false;

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

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

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

      if (totalGram >= M) {
        // 목표 무게와 같음 = 탈출
        isPossible = true;
        // 목표 무게와 같다고 해서 탈출 아님
        // 목표 무게를 넘었더라고 가격이 더 싸면 사기 때문
        answer = Math.min(answer, totalPrice);
      }
    }

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

}