출처

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

문제풀이

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

const [n, k] = input.shift().split(' ').map((a) => +a);
	const lines = input.map((a) => +a).sort();
	let max = Math.max(...lines);
	let min = 1;

while (min <= max) {
  let mid = parseInt((max + min) / 2);
  let howManyPieces = lines
    .map((line) => parseInt(line / mid))
    .reduce((a, b) => a + b, 0);
  if (howManyPieces >= k) {
    min = mid + 1;
  } else {
    max = mid - 1;
  }
}
console.log(max);

반복문을 이용하여 풀수도 있지만 이분탐색을 쓰지 않으면 시간초과가 나는 문제

max값은 가지고있는 랜선중 가장 큰 값, min은 1부터 시작한다.(1 - 802)

mid 값은 parseInt(max + min) / 2 로 정수값으로 구해주자.

현재 값 (mid) 로 랜선들을 다 나누어 몇개의 랜선을 만들수 있는지 모두 더해준다.

랜선의 개수가 만들고자 하는 개수(k)보다 많거나 같다면 자르는 단위를 늘려주어야한다. 그뜻은 현재 mid 값보다 자르는 값이 커져야 한다는 뜻, 즉 구하고자 하는 값은 배열의 우측에 위치하기 때문에 min 값을 mid+1 값으로 갱신한다.

랜선의 개수가 만들고자 하는 개수(k)보다 적다면 단위를 줄여야 하므로 구하고자 하는값은 mid의 왼쪽에 위치하므로 max 값을 mid-1로 갱신한다.

이것을 계속 반복하다보면 min 값이 max 값보다 커지게 되면 탐색을 종료한다.

구하고자 하는 랜선의 길이는 max 값이 된다.

마지막에 min+1 을 하기때문에 max가 구하고자 하는 랜선의 길이인것 같다.
(정확하게 아시는분 댓글 부탁드려요)