[백준 2258] 정육점 (JAVA)

https://www.acmicpc.net/problem/2258

2258번: 정육점

정렬과 그리디 문제였다.

가격 오름차순 정렬 -> 무게 내림차순 정렬 순으로 하고!첫번째 값(제일 싼 값)부터 총 무게값에 더하고,  총 가격에 해당 값의 가격을 넣는다.둘째 값부터는 이전 값의 가격이 꽁짜이기 때문에 총 가격을 둘째 값의 가격으로 넣는다.만일 이전 값의 가격과 같은 가격이라면, 그 고기도 사야하는 거기 때문에 총 가격에 둘째 값의 가격을 더한다.

 

필자는 answer에 Integer.MAX_VALUE를 넣고 포문이 끝난 후에도 answer 가 변동 없었다면 -1을 출력하게 했으나

*무게의 총 합과 가격의 총 합은 각각 2,147,483,647을 넘지 않는다. *

라는 주의사항이 있었다!!! Integer.MAX_VALUE값은  2,147,483,647이기 때문에 겹칠 수 있다..

따라서 answer 가 변동된 적이 있었는지 체크하는 변수를 따로 선언하여 문제를 해결했다.

 

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 Main {
	static class Node {
		int w, cost;

		Node(int w, int cost) {
			this.cost = cost;
			this.w = w;
		}
	}

	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.valueOf(st.nextToken());
		int M = Integer.valueOf(st.nextToken());
		Node[] list = new Node[N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			list[i] = new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
		}

		Arrays.sort(list, (a, b) -> {
			if (b.cost == a.cost)
				return b.w - a.w;
			else
				return a.cost - b.cost;
		});

		int totalPrice = -1;
		int totalGram = 0;
		int answer = Integer.MAX_VALUE;
		boolean isPossible = false;

		for (int i = 0; i < N; i++) {
			totalGram += list[i].w;

			if (i > 0 && list[i - 1].cost == list[i].cost) {
				totalPrice += list[i].cost;
			} else {
				totalPrice = list[i].cost;
			}

			if (totalGram >= M) {
				isPossible = true;
				answer = Math.min(answer, totalPrice);
			}
		}

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

}