[백준] - 2512 예산 (node.js)

문제링크

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const arr = fs.readFileSync(filePath).toString().trim().split("\n");

const n = Number(arr[0]);
const l1 = arr[1].split(" ").map(Number);
let m = Number(arr[2]);

let min = 1;
let max = Math.max(...l1);

while (min <= max) {
  const mid = Math.floor((min + max) / 2);
  let total = 0;

  for (let i = 0; i < n; i++) {
    if (l1[i] < mid) { // 예산 요청액이 적으면
      total += l1[i]; // 그냥 그대로 배분
    } else { // 크면
      total += mid; // mid를 배분
    }
  }

  if (total <= m) { // 근데 total값이 전체 예산보다 작으면
    min = mid + 1; // min 높이기
  } else { // 크면
    max = mid - 1; // max 줄이기
  }
}

console.log(max);

단순히 수학 문제로 풀다가 반례가 나와서 밑의 힌트를 보고 풀었다.. 이진탐색을 어떤 경우에 써야하는지에 대해 제대로 정리되지 않은 거 같다. 관련해서 정리해야겠다.

참고링크