[백준1654_자바스크립트(javascript)] - 랜선 자르기

🔴 문제

랜선 자르기

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const inputs = fs.readFileSync(path).toString().trim().split('\n');
const [n, k] = inputs[0].split(' ').map(Number);
const lines = inputs
  .slice(1)
  .map(Number)
  .sort((a, b) => a - b);

let left = 1;
let right = lines.at(-1);
let ans = 0;

while (left <= right) {
  const mid = Math.floor((left + right) / 2);
  let cnt = 0;

  for (const line of lines) {
    cnt += Math.floor(line / mid);
  }

  if (cnt < k) right = mid - 1;
  else {
    left = mid + 1;
    ans = mid;
  }
}

console.log(ans);

🟢 풀이

⏰ 소요한 시간 : -

문제를 보자마자 이전에 풀이했던 나무 자르기와 비슷하다는 생각이 들어 이분탐색으로 풀이했다.

랜선은 1부터, 가장 긴 랜선의 길이까지 자를 수 있으므로 left를 최소값 1로, right를 가장 긴 랜선의 길이로 초기화 해준뒤 이 두 값을 가지고 탐색해주면 된다.
두 값으로 중간값인 mid를 구해준다. 그리고 모든 랜선들을 mid값을 나누어 랜선의 개수를 체크한다. 즉 mid가 자를 랜선의 길이라고 했을 때 몇개가 나오는지 확인하는 것이다.
만약 랜선의 총 개수가 k보다 작으면 끝 값 right를 mid 보다 1 작은 값으로 세팅한 뒤 위 과정을 다시 반복한다.
만약 랜선의 개수가 k보다 크거나 같다면 mid가 일단 조건을 충족시키기 때문에 ans에 할당해주고, 더 최적화 된 값을 찾기 위해 left값을 mid 보다 1 큰 값으로 세팅한 뒤 위 과정을 다시 반복한다.

이 과정은 left가 right보다 커지게 되면 종료되며 매우 빠르게 정답을 구할 수 있다.

🔵 Ref