[level 2] 금고털이 (JAVA)

문제 요약

루팡은 배낭을 하나 메고 은행금고에 들어왔다. 금고 안에는 값비싼 금, 은, 백금 등의 귀금속 덩어리가 잔뜩 들어있다. 배낭은 W ㎏까지 담을 수 있다.
각 금속의 무게와 무게당 가격이 주어졌을 때 배낭을 채울 수 있는 가장 값비싼 가격은 얼마인가?
루팡은 전동톱을 가지고 있으며 귀금속은 톱으로 자르면 잘린 부분의 무게만큼 가치를 가진다.

---

문제 분석

보석을 가격이 높은 순서대로 정렬

배낭에 담을 수 있는 최대 무게인 bagWeight를 가지고, 배낭에 담을 수 있는 최대 가치를 계산

---

코드

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

public class Main {
    static class Jewelry implements Comparable<Jewelry> {
        int weight;
        int price;

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

        @Override
        public int compareTo(Jewelry jewelry) {
            return Integer.compare(jewelry.price, this.price);
        }

        @Override
        public String toString(){
            return weight +" " + price;
        }
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int bagWeight = Integer.parseInt(st.nextToken());
        int totalJewelryCnt = Integer.parseInt(st.nextToken());
        List<Jewelry> jewelryList = new ArrayList<>();
        for(int i = 0; i < totalJewelryCnt; i++){
            st = new StringTokenizer(br.readLine());
            int weight = Integer.parseInt(st.nextToken());
            int price = Integer.parseInt(st.nextToken());
            jewelryList.add(new Jewelry(weight, price));
        }
        Collections.sort(jewelryList);
        // System.out.println(jewelryList.toString());
        int valueResult = 0;
        for(Jewelry j : jewelryList){
            if(bagWeight <= 0){
                break;
            }
            if(bagWeight < j.weight){
                valueResult += j.price * bagWeight;
                bagWeight = 0;
            }
            else {
                valueResult += j.price * j.weight;
                bagWeight -= j.weight;
            }
        }
        System.out.println(valueResult);
    }
}

---

정리

새로 배운 내용

없음

개선할 점

DP?

더 찾아볼만한 사항

knapsack문제를 본게 오랜만이다. 이참에 다양한 경우를 찾아봐야겠다.

---