[백준 2512] 예산 with Node.js

문제 링크

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

2512번: 예산

풀이

const solve = (input, N, M) => {
  input.sort((a, b) => a - b);
  let high = input[N-1];
  let low = 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    const sum = input.reduce((acc, v) => acc + (v <= mid ? v : mid), 0);
    if (sum <= M) low = mid + 1;
    else high = mid - 1;
  }
  console.log(high);
};

const [N, ...input] = require('fs').readFileSync('/dev/stdin').toString().trim().split(/\s+/).map(v => +v);
const M = input.pop();
solve(input, N, M);

배정되는 예산은 1(예산의 최솟값)과 최대 요청 금액 사이의 정수이다.

따라서, 1과 요청 금액들 중에서의 최대 금액 사이에서 이진 탐색을 통해 총 예산을 넘지 않는 최대 예산을 구할 수 있다.