문제 링크

풀이

dp 문제로 유명한 배낭문제와 유사하지만 귀금속을 잘라 크기를 조절할 수 있기 때문에 더 간단한 문제이다.
그리디 알고리즘을 사용하여 풀이하면 된다. 금속 클래스를 정의하고 리스트에 담은 후 무게당 가격이 비싼 순서대로 정렬한다. 남은 배낭 무게와 금속의 무게를 비교해가며 통째로 집어 넣거나 잘라서 넣어주면 된다.

코드

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

public class Main {
    static int W, N;
    static List<Metal> metals;
    static int result = 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());
        metals = new ArrayList<Metal>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int weight = Integer.parseInt(st.nextToken());
            int price = Integer.parseInt(st.nextToken());
            metals.add(new Metal(weight, price));
        }

        metals.sort((m1, m2) -> Integer.compare(m2.price, m1.price));
        for (Metal m : metals) {
            int weight = m.weight;
            int price = m.price;
            if (W < weight) {
                result += price * W;
                W = 0;
                break;
            }
            result += price * weight;
            W -= weight;
        }
        System.out.println(result);
    }

    public static class Metal {
        int weight;
        int price;

        public Metal(int weight, int price) {
            this.weight = weight;
            this.price = price;
        }
    }
}