[javaScript] Softeer - 금고털이

https://softeer.ai/class/devcrew/study/resource/detail/description/6288?id=155&resourceId=80

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

 

 

언어별 시간/메모리

언어시간메모리

JavaScript	3초	256MB
C	1초	256MB
C++	1초	256MB
Java	2초	256MB
Python	3초	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

 

const readline = require('readline');
let rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
})

let W, N;
let Nlist = [];//{m: M, p: P, mp: m*p}
let count = 0;
rl.on('line', function(x){
    if(count == 0){
        [W, N] = x.split(' ').map(Number);
    }else{
        let [M, P] = x.split(' ').map(Number);
        Nlist.push({m: M, p: P});
        if(count == N){
            rl.close();            
        }
    }
    count++;
}).on('close', function(){
    main();
})


function sortF(){
    Nlist = Nlist.sort(function(a, b) {
        return b.p - a.p;
    })   
}

function main(){
    sortF();
    let total = 0;
    for(let i = 0; i < Nlist.length; i++){
        let m = Nlist[i].m;
        let p = Nlist[i].p;
        
        if(W == 0){
            break;
        }else if(m <= W){
            W -= m;
            total += (m*p);
        }else{
            total += (W*p);
            break;
        }        
    }
    console.log(total);
}