백준, 2512 예산 javascript

백준,2512 예산

📖 https://www.acmicpc.net/problem/2512

👨‍💻 문제 풀이

• 일반적인 이분탐색
• 최댓값을 구하는 것도 나무자르기, 랜선 문제의 연장선이다.

💻 제출한 코드

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');

const [N, request, total] = [+input[0], input[1].split(' ').map(Number), +input[2]];


request.sort((a,b) => a-b);

let left = 0;
let right = request[request.length-1];
let answer = Number.MIN_SAFE_INTEGER;
while(left <= right) {
    let mid = Math.floor((left + right)/2);

    let possible = 0;
    for(let x of request) {
        if( x > mid ) possible += mid;
        else possible += x;
    }

    if(total >= possible) {
        // 예산 배정이 가능한 경우
        if(mid > answer) answer = mid;
        // answer은 최댓값
        left = mid + 1;
    } else {
        right = mid -1;
    }
}

console.log(answer);

이번 문제를 풀면서,

• 처음 이분탐색 풀면서 이거 어떻게해.. 라고 생각했는데
• 점차점차 풀어가다 보니까, 알고리즘이 비슷비슷해서 결과적으로 비슷한 로직임을 발견할 수 있었다.
• 그래도 아직까지는 실버난이도니까... 윗 난이도는 어렵겠지 😂