[Softeer] 금고털이 - JAVA

금고털이 문제 바로가기

풀이 

이번문제는 문제대충 읽고 배낭문제로 접근했었는데 자세히보니 톱으로 자를수 있다?...
근데 설명이 좀 난해한 부분이 있는 것 같다.
무게당 가격이란 단어때매 햇갈렸다..
무게당 가격의 의미는 해당 보석의 가격이 아니라 1g당 가격을 의미한다.
즉, 높은 무게로 정렬을 하고 배낭을 가득채워주면 된다
그러므로 정렬, 그리디 알고리즘으로 접근하면 된다.

로직은 크게 어려울게 없다.
정렬 후 배낭에 보석들을 채워가며 넣어주다가 
배낭이 가득차면 멈추면된다.

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

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

        int[][] arr = new int[N][2];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }
        
        // 가격이 높은순으로 정렬
        Arrays.sort(arr, ((o1, o2) -> o2[1] - o1[1]));

        int answer = 0;
        int totalWeight = 0;

        for (int i = 0; i < N; i++) {
            int weight = arr[i][0];
            int price = arr[i][1];

            if (totalWeight + weight <= W) {
                totalWeight += weight;
                answer += price * weight;
            } else {
                answer += price * (W - totalWeight);
                break;
            }
        }

        System.out.println(answer);


    }
}