[구름톤 챌린지 15일차] 과일 구매

이번 문제는 그리디 문제이다. 처음엔 동적 프로그래밍 문제라고 생각해서 어떻게 테이블을 만들지 생각했었는데 굳이 동적 프로그래밍을 위한 테이블을 따로 생성하지 않더라도 그리디 접근 방식으로 풀 수 있다는걸 알게 되었다.문제 해결 방법은 간단하다. 일단 주어진 조건인 쓸 수 있는 금액이고 그 금액 한도 내에서 가격 대비 포만감이 높은 과일을 먼저 사 나가는 방식으로 풀면 된다. 만약 쓸 수 있는 금액보다 과일의 가격이 높다면 과일 가격의 최소단위로 포만감을 나눠서 조각 단위로 구매하면 된다.

 

배운 점

10의 9제곱 이상인 수를 다룰때 int형이 아닌 long 타입을 활용해야 한다는 걸 알게 되었다. 그리디 문제를 해결하기 위한 접근 방식도 알게 되었다. Collections.sort()로 내림차순으로 정렬하는 방법을 다시금 알게 되었다.

 

어려웠던 점

처음 어떻게 해결할 지 고민했던걸 제외한다면 크게 어려웠던 부분은 없었던거 같다.

 

느낀 점

자바 언어의 메소드에 좀더 친숙해져야겠다고 생각했다.

 

 

import java.io.*;
import java.util.*;
class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] NK = br.readLine().split(" ");
		int N = Integer.parseInt(NK[0]);
		int K = Integer.parseInt(NK[1]);
		List<double[]> valueSatiety = new ArrayList<>();
		for(int i = 0; i < N; i++){
			String[] PC = br.readLine().split(" ");
			int P = Integer.parseInt(PC[0]);
			int C = Integer.parseInt(PC[1]);
			double [] vs = new double[2];
			vs[0] = (double) C / P;
			vs[1] = (double) P;
			valueSatiety.add(vs);
		}
		long result = 0;
		Collections.sort(valueSatiety, (a, b) -> Double.compare(b[0], a[0]) != 0 ? Double.compare(b[0], a[0]) : Double.compare(b[1], a[1]));
		for(int i = 0; i < N; i++){
			double[] temp = valueSatiety.get(i);
			
			double v = temp[0];
			double a = temp[1];
			double toBuy = Math.min(a, K);
			K -= toBuy;
			result += toBuy * v;
		}
		System.out.println((long) Math.floor(result));
	}
}