백준1654 - 랜선 자르기 (이분탐색) node.js

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

해당 문제는 랜선의 갯수 N, 필요한 랜선의 갯수M 그리고 N개의 랜선 각각의 길이가 주어질 때, 필요한 랜선의 갯수 M을 만들 수 있는 최대 길이의 랜선을 구하는 문제다.

문제 풀이 방식

이분탐색에서 활용하기 위한 범위를 설정한다. 최소 범위는 0, 최대 범위는 주어진 랜선의 길이 중 가장 큰 것으로 초기화한다. (최대 범위가 랜선의 길이 중 가장 큰 값일 경우 가져갈 수 있는 랜선의 갯수는 최소가 되기 때문)

이후 while문에서는 중간값을 구한 뒤, 해당 중간값을 자를 랜선의 길이로 하여  만들 수 있는 총 갯수를 구한다.

그리고 이 갯수를 counts라고 할 때, 해당 값이 문제에서 필요로 하는 랜선의 갯수 m보다 크거나 같을 경우 최소 범위를, 작을 경우는 최대 범위를 더 좁게 수정한다.

같을 경우 답을 리턴하는 것이 아니라, 크거나 같을 경우에도 범위를 좁히는 이유는 다양할 수 있겠지만 이 문제의 경우 최적의 값을 찾는 것이 아닌 조건을 만족하는 값 중에서 가장 큰 값을 찾는 것이 목표기 때문에,

start의 범위를 더 큰 값으로 수정하여 해당 탐색을 모두 진행한 뒤 end를 결괏값으로 출력한다. (최댓값을 찾고자 하는 것이므로, start의 범위를 최대한 높이는 방식으로 모든 탐색을 진행하는 것이라 이해하면 좋다.)

이때 end는 모든 탐색이 완료되었을 때 조건을 만족하는 최댓값이 담겨 있는 변수기도 하며, while문 탈출조건이 (start > end)이므로 start - 1 과 end 값은 같은 값을 지닌다. 

전체 소스 코드

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

function solution(data) {
  const [_, m] = data.shift().split(" ").map(Number);
  const arr = data.map(Number);

  let start = 0;
  let end = Math.max(...arr);

  while (start <= end) {
    const mid = Math.floor((start + end) / 2);
    const counts = arr.reduce((acc, cur) => acc + Math.floor(cur / mid), 0);
    if (counts >= m) start = mid + 1;
    else end = mid - 1;
  }

  console.log(end);
}

solution(input);