[Softeer/소프티어][Level3]금고털이(Java)

https://softeer.ai/practice/info.do?idx=1&eid=395 

Softeer

[문제]

루팡은 배낭을 하나 메고 은행금고에 들어왔다. 금고 안에는 값비싼 금, 은, 백금 등의 귀금속 덩어리가 잔뜩 들어있다. 배낭은 W ㎏까지 담을 수 있다.

 

각 금속의 무게와 무게당 가격이 주어졌을 때 배낭을 채울 수 있는 가장 값비싼 가격은 얼마인가?

 

루팡은 전동톱을 가지고 있으며 귀금속은 톱으로 자르면 잘려진 부분의 무게만큼 가치를 가진다.

 

[풀이]

import java.util.*;
import java.io.*;


public class Main
{
   static int W; // 1 <= W <= 10000; 배낭의 무게
	static int N; // 1 <= N <= 1000000; 귀금속의 종류
	static int[][] MP; // 1<= M , 각 귀금속의 무게, 무게당 가격
	static int PRICE = 0;
	
	public static void main(String[] args) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		W = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		
		MP = new int[N][2];
		
		for (int i = 0; i < N; i++)
		{
			st = new StringTokenizer(br.readLine());
			MP[i][0] = Integer.parseInt(st.nextToken());
			MP[i][1] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(MP, (o1, o2) -> Integer.compare(o2[1], o1[1]));
		
		int nIndex = 0;
		
		while (true)
		{
			if (W == 0)
				break;
			
			if (MP[nIndex][0] < W)
			{
				PRICE += (MP[nIndex][0] * MP[nIndex][1]);
				W -= MP[nIndex][0];
				nIndex++;
			} else
			{
				PRICE += (W * MP[nIndex][1]);
				W = 0;
			}
		}
		System.out.println(PRICE);
	}
}