Softeer 금고털이 java

문제

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

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

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

제약조건

1<=N<=10^6인 정수
1<=W<=10^4인 정수
1<=Mi, Pi<=10^4인 정수

입력형식

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

출력형식

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

입력예제1

100 2
90 1
70 2

출력예제1

170

tip

시간 초과를 해도 틀렸다고 표현.
이 문제가 요구하는 것은 1.BufferedReder를 쓰는가 or 2.Sorting에서 시간을 단축했는가.
2.는 PriorityQueue를 사용해야만 정답이 인정되는 것으로 추측.

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

public class Main
{
	public static void main(String args[]) throws IOException
    {
    
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int total = INteger.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        
        PriorityQueue<Jewel> queue = new PriorityQueue<Jewel>();
        
        // 너무 간단한 문제라 그냥 array 써서 sorting 하면 오답이 나온다?
        // int[][] jewelry = new int[N][2]; // jewelry[i][0] : 무게
        // jewelry[i][1] : 가격
        for(int i=0; i<N; i++){
        	st = new StringTokenizer(br.readLine(), " ");
            //jewelry[i][0] = Integer.parseInt(st.nextToken());
            //jewelry[i][1] = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            int price = Integer.parseInt(st.nextToken());
            queue.offer(new Jewel(weight, price));
        }
        
        //Array.sort(jewelry, (o1, o2) -> o1[1] < o2[1] ? 1 : -1);
        
        int result = 0;
        
        while(!queue.isEmpty()){
        	Jewel jewel = queue.poll();
            if(total < jewel.weight){
            	result = result + total * jewel.price;
                break;
            } else {
            	result = result + jewel.weight * jewel.price;
                total = total - jewel.weight;
            }
        }
        
        System.out.print(result + "");
     }  
     
     public static class Jewel implements Comparable<Jewel>{
     	public int weight;
        public int price;
        public Jewel(int weight, int price){
        	this.weight = weight;
        	this.price = price;
        }
     
     	@Override
        public int compareTo(Jewel jewel){
        	return this.price < jewel.price ? 1 : -1;
        }
     }
  }