링크

링크텍스트

문제

은혜는 정육점에서 고기를 사려고 한다. 보통 정육점에서는 자신이 원하는 양을 이야기하면 그 양만큼의 고기를 팔지만, 은혜가 방문한 정육점에서는 세일 행사를 하고 있었기 때문에 N 덩어리의 고기를 이미 잘라놓고 판매하고 있었다.

각각의 덩어리들은 이미 정해져 있는 무게와 가격이 있는데, 어떤 덩어리를 샀을 때에는 그 덩어리보다 싼 고기들은 얼마든지 덤으로 얻을 수 있다(추가 비용의 지불 없이). 또한 각각의 고기들은 부위가 다를 수 있기 때문에 비용과 무게와의 관계가 서로 비례하는 관계가 아닐 수도 있다. 은혜는 이러한 점을 고려하지 않고, 어느 부위든지 자신이 원하는 양만 구매하면 되는 것으로 가정한다. 또한 만약 가격이 더 싸다면 은혜가 필요한 양보다 더 많은 고기를 살 수도 있다.

각 덩어리에 대한 정보가 주어졌을 때, 은혜가 원하는 양의 고기를 구매하기 위해 필요한 최소 비용을 계산하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 100,000), M(1 ≤ M ≤ 2,147,483,647)이 주어진다. N은 덩어리의 개수를 의미하고, M은 은혜가 필요한 고기의 양이다. 다음 N개의 줄에는 각 고기 덩어리의 무게와 가격을 나타내는 음 아닌 두 정수가 주어진다. 무게의 총 합과 가격의 총 합은 각각 2,147,483,647을 넘지 않는다.

출력

첫째 줄에 답을 출력한다. 불가능한 경우에는 -1을 출력한다.

풀이

문제를 이해하는데 하루정도 걸린것 같다.
그래서 주말에 무조건 다시 복습!!!

참조 링크

1. 고기 무게, 가격 입력 후 정렬하기

• (가격, 무게) 순으로 가격은 오름차순, 무게는 내림차순으로 정렬 => 앞에서부터 탐색하면서 가격은 적으면서 무게가 큰 고기를 선택하기 위함

2. 고기의 무게를 더해가면서 해당 고기가 이전에 탐색한 고기의 가격과의 일치 여부 확인하기 => 이 문제의 핵심 예외케이스

• 이전 고기의 가격과 일치할 경우 same 변수에 해당 값을 더하기

3. 현재까지 고기의 무게가 M 이상일 경우 결과값(ans) 갱신하기

• 현재까지 탐색한 고기 중 가격이 동일한 고기가 있을 경우 해당하는 값(same) 더하기

• 현재까지 고기의 무게가 M 이상이면서 최소의 가격으로 갱신

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class practice {
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		int n=Integer.parseInt(st.nextToken()); //덩어리의 개수
		int m=Integer.parseInt(st.nextToken()); //필요한 고기의 양
		int arr[][]=new int[n][2];
		int answer=Integer.MAX_VALUE;
		
		
		for(int i=0; i<n; i++)
		{
			StringTokenizer st1=new StringTokenizer(br.readLine());
			int weight=Integer.parseInt(st1.nextToken());
			int price=Integer.parseInt(st1.nextToken());
			arr[i][0]=weight;
			arr[i][1]=price;
		}
		
		
		
		//0이 무게, 1이 가격
		//무게 내림차순, 가격 오름차순
		Arrays.sort(arr, new Comparator<int[]>() {
			public int compare(int[] o1, int[] o2)
			{
				if(o1[1] > o2[1]) //가격 오름차순
					return 1;
				
				else if(o1[1] == o2[1])
					return Integer.compare(o2[0], o1[0]);//내림차순
				
				else //정렬 X
					return -1;
			}
		});	
		
		//temp : 무게의 누적 총 합을 구할 변수,
		//same : 가격이 같을 때 가격의 누적 합
		int temp=0, same=0;
		boolean stop=false;
		
		for(int i=0; i<n; i++)
		{
			temp+=arr[i][0]; //무게 누적 총합
			if(i>=1 && arr[i-1][1] == arr[i][1])//이전과 가격이 같을때
				same+=arr[i][1];
			else same=0; //가격이 다를때
			
			if(temp>=m) //조건 m보다 같거나 클 때
			{
				stop=true; //표시
				answer=Math.min(answer, arr[i][1]+same);
			}
			
		}
		if(stop)
			System.out.println(answer);
		else
			System.out.println(-1);
		
		
	}
}