BOJ - 2258 정육점

leehyunjon·2022년 6월 29일

boj 그리디 정렬

Algorithm

목록 보기

89/162

Problem

Solve

첫번째 풀이에선 가격을 기준으로 오름차순 정렬, 무게를 기준으로 오름차순 정렬을 한 후, 무게를 누적합을 구하여 누적합이 M이상이 되었을 경우의 가격을 반환하도록 구현하였는데 틀렸다.

이 구현의 반례는
3 8
4 2
4 2
1 3 이 된다.

놓치고 있던 부분은 같은 가격을 구성할 때 M이상인 것을 찾기 위해서는 같은 가격인 고기들의 가격을 합해서 비교해야한다.

일단 이 문제를 해결하기 위해서는 정렬을 먼저 생각해야한다.
최소의 비용을 얻어야하고 같은 비용일때 가격을 합하면서 M과 고기의 크기를 비교해야하기 때문에 가격을 기준으로 오름차순 정렬하고, 같은 가격일때 크기가 큰 고기의 비용부터 비교해야 최소 비용으로 고기 크기를 비교할수 있기 때문에 크기를 기준으로 내림차순 정렬해야한다.

만약 크기 기준 오름차순 정렬시
4 3
1 2
2 2
3 2
5 7 의 반례가 있다.

정렬 한 후에는 고기를 순차적으로 돌면서 해당 비용으로 구할 수 있는 고기의 크기를 구하고 해당 고기의 비용이 이전 고기의 비용과 같다면 고기 비용을 더해주고 아니라면 해당 고기의 비용으로 갱신한다.

그 후, 해당 고기의 크기가 M이상이라면 조건에 만족하는 비용의 최소를 구한다.
이유는 이전에 구했던 조건에 맞는 고기의 비용이 현재 조건을 만족하는 고기의 비용보다 크거나 작을 수 있기 때문이다.

Code

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.StringTokenizer;

public class 정육점 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		Meat[] meats = new Meat[N];

		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int s = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			meats[i] = new Meat(s, c);
		}

		//비용 오름차순정렬, 크기 내림차순 정렬
		Arrays.sort(meats);

		int answer = Integer.MAX_VALUE;
        //현재 구매할수 있는 고기의 크기
		int size = 0;
        //현재 고기크기를 구매할 수 있는 비용
		int cost = 0;
        //M이상의 고기를 구매할수 있는지 여부
		boolean isPossible = false;
		for (int i = 0; i < N; i++) {
			Meat currentMeat = meats[i];

			//현재 고기로 살수 있는 최대 크기
			size += currentMeat.s;

			//이전 고기와 비용이 동일하다면 돈을 지불하고 구매할수 있다.
			if(i>0 && currentMeat.c == meats[i-1].c){
				cost += currentMeat.c;
			}
            //이전 고기와 비용이 동일하지 않다면 이전까지의 고기는 공짜로 구매할수 있다.
            //즉 현재 고기의 비용만 있다면 현재 size의 고기를 구매할수 있다.
            else{
				cost = currentMeat.c;
			}

			//현재 고기가 M이상이라면 조건에 맞는 고기의 비용 중 최소를 구해야한다.
			if(size >= M){
				answer = Math.min(answer, cost);
                //M이상 고기 구매 가능
				isPossible = true;
			}
		}

		if(!isPossible) answer = -1;

		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
	}

	static class Meat implements Comparable<Meat> {
		int s;
		int c;

		public Meat(int s, int c) {
			this.s = s;
			this.c = c;
		}

		@Override
		public int compareTo(Meat o1) {
			int result = this.c - o1.c;
			if (result == 0) {
				result = o1.s - this.s;
			}
			return result;
		}
	}
}