[200일차]boj1654 node.js

백준1654 랜선자르기

문제링크

CODE

const readline = require("readline");
 
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});
const input = [];
rl.on("line", function (line) {
    input.push(input.length ? +line : line);
    const [K, N] = input[0].split(" ");
    if (input.length === +K + 1) {
        input.shift();
        let length = 0;
        const binarySearch = (left, right) => {
            while (left <= right) {
                let mid = ~~((left + right) / 2);
                let wire = input.reduce((sum, w) => {
                    return sum + ~~(w / mid);
                }, 0);
                if (wire >= N) {
                    if (mid > length) {
                        length = mid;
                    }
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        };
        binarySearch(
            1,
            input.reduce((max, n) => {
                return n > max ? n : max;
            }),
        );
        console.log(length);
        rl.close();
    }
}).on("close", function () {
    process.exit();
});

description

처음엔 길이를 하나씩줄이는 방법으로 풀었으나 시간초과가 났고,
이분탐색부분을 재귀로 구현을하면 스택사이즈 오류가 난다.
반복문을 활용해서 풀어주고,
이분탐색의 두번째 인자는 랜선중 가장 긴값을 넣은것..
간혹 다량의 값을 Math.max의 인자로 넣으면 백준에서 오류남..

이 문제를 기점으로 실버찍었다!

자축!