[Greedy]정육점(백준 2258번), 자바(ㅁ)

2258번: 정육점 (acmicpc.net)

2258번: 정육점

 

 

 

import java.util.*;

public class Main {
	
	
	public static void main(String[] args) {
		
		int N,M;
		Scanner sc=new Scanner(System.in);
		N=sc.nextInt();
		M=sc.nextInt();
		
		ArrayList<Meat> arr=new ArrayList<>();
		for(int i=0;i<N;i++) {
			int a=sc.nextInt();
			int b=sc.nextInt();
			arr.add(new Meat(a,b));
		}
		
		
		Collections.sort(arr, new Comparator<Meat>() {

			@Override
			public int compare(Meat o1, Meat o2) {
				// TODO Auto-generated method stub
				if(o1.price==o2.price) return o2.cnt-o1.cnt;
				else return o1.price-o2.price;
			}
			
		});
		
	boolean check=false;
	int prices=0;
	int sum=0;
	int answer=Integer.MAX_VALUE;
		for(int i=0;i<N;i++) {
			if(i>=1 && arr.get(i-1).price==arr.get(i).price) prices+=arr.get(i-1).price;
			else prices=0;
			
			if(sum+arr.get(i).cnt>=M) {
				prices+=arr.get(i).price;
				check=true;
				answer=Math.min(prices, answer);
			}
			else {
				sum+=arr.get(i).cnt;
			}
			
		}
		
	if(!check) answer=-1;
	System.out.println(answer);
	
	}

	
	static class Meat{
		int cnt;
		int price;
		
		Meat(int cnt, int price){
			this.cnt=cnt;
			this.price=price;
		}
	}
}

 

 

내가 생각한 추가 풀이 

for(int i=1;i<N;i++){
		if(arr.get(i).price==arr.get(i-1).price) prices+=arr.get(i).price;
		else prices=arr.get(i).price;


		if(sum+=arr.get(i)>=M){
			answer=Math.min(answer,prices);
		}

		else 
			sum+=arr.get(i).cnt;

	}