[Softeer] 금고털이 java

문제

문제링크
난이도: level 2
알고리즘 분류: 그리디, 정렬

통과 코드

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


public class Main
{
    static class Metal {
        int g, gramPerPrice;
        
        public Metal(int g, int gramPerPrice) {
            super();
            this.g = g;
            this.gramPerPrice = gramPerPrice;
        }
    }
    static int W, N;
    static Metal[] metals;
    public static void main(String args[]) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        W = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        metals = new Metal[N];
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            metals[i] = new Metal(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }
        //가격이 비싸고 + 무게가 높은 애들 순으로 정렬
        Arrays.sort(metals, new Comparator<Metal>() {
            @Override
            public int compare(Metal o1, Metal o2) {
                if(o1.gramPerPrice == o2.gramPerPrice) {
                    return o2.g - o1.g;
                }
                return o2.gramPerPrice - o1.gramPerPrice;
            }
        });
        //System.out.println(Arrays.toString(metals));
        int sub=W, price=0;
        for(int n=0; n<metals.length; n++) {
            if(sub < metals[n].g) {
                price += sub * metals[n].gramPerPrice;
                break;
            } else {
                price += metals[n].g * metals[n].gramPerPrice;
                sub -= metals[n].g;
            }
        }
        System.out.println(price);
    }
}

dp의 대표적인 문제인 knapsack처럼 자를 수 없는 구조가 아니므로 일반 정렬로 풀어야겠다고 생각함.
사용자 정의 클래스를 만든 후 배열을 생성하여 값을 받고 나서 정렬을 해주었다.
1. g당 가격이 높은 순으로 정렬을 실행한 후
2. 가격이 같을 땐 무게가 무거운 순으로 정렬되도록 Comparator를 Override 해주었다.

(이때 항상 인텔리제이에서 자동완성으로 해주던 기본적인 오버라이드 코드가 생각이 나지 않아 참고했다 ..)

그 후 계산 코드를 구현하여 문제를 풀었다.

결과