(JAVA)[softeer] 금고털이

 

Softeer

 

소프티어, 금고털이

🔥 난이도 : LEVEL 2

이번 문제는 입력받을 금고를 표기할 Class 사용한 Greedy 알고리즘을 사용하여 풀어봤다.

 

📚 프로세스

주의할 점 몇가지에 대해 설명한다.

초기화 및 선언

무게와 금속의 종류를 입력받고 그 값을 Metal 이라는 class를 생성해준다. 이는 추후에 정렬을 하기 위해 작성한 코드이다.

 

정렬

가격이 같다면 무게 오름차순, 이외에는 가격 내림차순으로 정렬해준다. 이는 가장 비싼 가격을 출력하기 위함이다.

정리를 해보면 한정된 가방 무게에 가장 가치가 비싼 금속으로 채워넣어야 한다.

그렇기 때문에 가격이 비싼 것부터 가방을 가득 채울 때까지 넣어준다는 의미로 로직을 구성하였다.

 

✳️ 문제풀이

두 가지 가정이 있다. 

1. 가방의 무게가 넣으려는 금속의 무게보다 클 경우

2. 그 외의 경우

 

1번의 경우에는 금속 전체를 넣어주면 된다. 2번의 경우에는 가방의 무게만큼 금속을 넣어주고 루프를 종료시키면 된다.

 

✅ 전체 코드

class 의 사용 & Array.sort의 정의 이 두 가지만 잘 정의해서 사용하면 어렵지 않게 풀 수 있는 문제였다.

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

class Metal {
    int weight;
    int price;

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

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

        W = Integer.parseInt(st.nextToken()); // 넣어야 할 무게
        N = Integer.parseInt(st.nextToken());

        Metal[] m = new Metal[N];
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            m[i] = new Metal(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        Arrays.sort(m, new Comparator<Metal>() {
            @Override
            public int compare(Metal o1, Metal o2) {
                // 가격이 같다면 무게 오름차순
                if (o1.price == o2.price) {
                    return o1.weight - o2.weight;
                }
                // 가격 내림차순
                return o2.price - o1.price;
            }
        });

        int answer = 0;
        for(Metal e : m) {
            if(W >= e.weight) {
                answer += e.weight * e.price;
            } 
            else {
                answer += W * e.price;
                break;
            }

            W -= e.weight;
        }
        

        System.out.println(answer);
    }
}