2258번: 정육점
첫째 줄에 두 정수 N(1 ≤ N ≤ 100,000), M(1 ≤ M ≤ 2,147,483,647)이 주어진다. N은 덩어리의 개수를 의미하고, M은 은혜가 필요한 고기의 양이다. 다음 N개의 줄에는 각 고기 덩어리의 무게와 가격을 나
www.acmicpc.net
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;
}