[JAVA] 금고털이

https://softeer.ai/practice/6288

Softeer - 현대자동차그룹 SW인재확보플랫폼

언어별 시간/메모리

 

JavaScript	3초	256MB
C	1초	256MB
C++	1초	256MB
Java	2초	256MB
Python	3초	256MB
C#	2초	256MB
Kotlin	2초	256MB
Go	2초	256MB
Swift	2초	256MB

루팡은 배낭을 하나 메고 은행금고에 들어왔다. 금고 안에는 값비싼 금, 은, 백금 등의 귀금속 덩어리가 잔뜩 들어있다. 배낭은 W ㎏까지 담을 수 있다.

 

각 금속의 무게와 무게당 가격이 주어졌을 때 배낭을 채울 수 있는 가장 값비싼 가격은 얼마인가?

 

루팡은 전동톱을 가지고 있으며 귀금속은 톱으로 자르면 잘려진 부분의 무게만큼 가치를 가진다.

제약조건

1 ≤ N ≤ 106인 정수

1 ≤ W ≤ 104인 정수

1 ≤ Mi, Pi ≤ 104인 정수

입력형식

첫 번째 줄에 배낭의 무게 W와 귀금속의 종류 N이 주어진다. i + 1 (1 ≤ i ≤ N)번째 줄에는 i번째 금속의 무게 Mi와 무게당 가격 Pi가 주어진다.

출력형식

첫 번째 줄에 배낭에 담을 수 있는 가장 비싼 가격을 출력하라.

입력예제1

100 2 90 1 70 2

출력예제1

170

 

 

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

public class Main {

  static class Jewl implements Comparable<Jewl> {
    int weight;
    int price;

    public int getPrice(int targetWeight) {
      return targetWeight * this.price;
    }

    @Override
    public int compareTo(Jewl b) {
      // 킬로당 가격 순으로 정렬
      return b.price - this.price;
    }
  }

    public static void main(String[] args) {
      Scanner s = new Scanner(System.in);

      int W = s.nextInt(); // 배낭의 최대 무게
      int N = s.nextInt(); // 귀금속 수
      PriorityQueue<Jewl> pq = new PriorityQueue<>();

      for(int i=0; i<N; i++) {
        Jewl j = new Jewl();
        j.weight = s.nextInt();
        j.price = s.nextInt();
        pq.add(j);
      }


      // 가격 순으로 담기
      int tmpW = 0; // 현재 가방 내 무게
      int answer = 0;
      
      for(int i=0; i<N; i++) {
        Jewl target = pq.poll();
        if(tmpW + target.weight <= W) {
          // 가방이 여유로움
          tmpW += target.weight;
          answer += target.getPrice(target.weight);
          if(W == tmpW) {
            break;
          }
        }
        else {
          // 가방이 여유롭지 못함
          answer += target.getPrice(W - tmpW);
          break;
        }
      }

      System.out.println(answer);
    }
}