[백준 node.js] 2437번_저울

백준 그리디 알고리즘 2437번_저울

난이도 : 골드III

 

문제 설명

입출력

 

문제 풀이 : 약간의 수학적 지식이 필요한 문제인거 같다. 맨처음에 모든 경우의 수를 다 구해서 풀어야하는줄 알았다..

다른 블로그를 참고하니 그렇게 접근하는 것이 아니였다.ㅠㅠㅠ

우선 추를 오름차순으로 정렬해준다. 그 후 반복문을 현재 추의 무게와 누적합 +1 값을 비교해준다.

누적합 +1 이 현재 추보다 크거나 같다면 이는 누적합 +1 까지 표현이 가능하다는 의미이다.

누적합 +1이 현재 추보다 작다면 이는 표현이 불가능하다는 것을 의미한다.

 

//골드3 저울
function solution(n, list) {
    //오름차순
    list.sort(function(a,b){
        return a - b;
    })

    let sum = 0;
    for(i of list){
        //누적합 +1이 현재 인덱스의 값보다 크거나 같다면 누적합 +1 까지 표현이 가능하다.
        if(sum + 1 >= i){
            sum += i; 
        }
        //누적합 +1이 현재 인덱스의 값보다 작다면 이는 누적합 +1 이 표현이
        //불가능하다는 의미이다.
        else{
            break;
        }
    }
    //출력시 누적합 +1을 해준다.
    console.log(sum+1);
}

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

let input = [];
rl.on("line", function (line) {
   input.push(line)
}).on("close", function () {

    let n = parseInt(input[0]);
    let list = input[1].split(" ").map((el) => parseInt(el));
    solution(n, list);
    process.exit();
});