[Softeer] 금고털이 - JAVA

1. 문제

Softeer

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

 

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

 

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

---

2. 풀이

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


public class Main
{
    public static void main(String args[]) throws Exception
    {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());
        
        int W = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        ArrayList<int[]> list = new ArrayList<>();
        for(int i=0;i<N;i++){
            st = new StringTokenizer(in.readLine());
            list.add(new int[]{Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())});
        }

        Collections.sort(list,(o1,o2)->o2[1]-o1[1]);
        
        int answer = 0;

        for(int[] item:list){
            if(W<=item[0]){
                answer += W*item[1];
                break;
            }else{
                answer += item[0]*item[1];
                W-=item[0];
            }
        }

        System.out.println(answer);
    }
}

---

3. 결과