1654 랜선 자르기

문제 분석

알고리즘: 이진탐색

K개의 랜선으로 N개의 같은 길이 랜선을 만드는 문제이다. 이진 탐색(이분 탐색)을 활용해

1. 중간값(mid)으로 나눠진 값이 예제로 주어진 필요한 랜선의 수보다 높거나 같을 경우들
2. ①번의 경우들 가운데, 중간값(mid)이 가장 큰 경우를 구한다.

단, 이진탐색을 하기 위해서는 필수적으로, 주어진 수들이 정렬되어 있어야한다.

문제 풀이

const input = require('fs').readFileSync('./input.txt').toString().trim().split('\n');
const [k, n] = input.shift().split(' ').map(Number);

const lines = input.map(Number).sort((a, b) => a - b); // 1

let min = 0; // 2
let max = lines[k - 1]; // 2

let answer = 0;

while (min <= max) {
  const mid = Math.floor((min + max) / 2); // 3
  const pieces = input.reduce((acc, cur) => acc + Math.floor(cur / mid), 0); // 4

  if (pieces >= n) {
    // 5
    min = mid + 1; // 6
    if (mid > answer) answer = mid; // 7
  } else {
    max = mid - 1; // 8
  }
}

console.log(answer);

1. 주어진 수들을 오름차순으로 정렬한다.
2. 최소값(min)을 0으로 초기화하고, 최대값(max)은 주어진 수 가운데 가장 큰 값으로 초기화한다.
3. 이진탐색의 핵심인 중간값(mid)을 구한다. 소수점이 나올 수 있으므로 Math.floor를 사용해 소수점을 버린다.
   1. 중간값 이전의 수들 가운데 조건에 만족하는 수가 있다면, 중간값 이후의 값들은 탐색할 필요가 없다.
   2. 반대로, 중간값 이후의 수들 가운데 조건에 만족하는 수가 있다면, 중간값 이전의 값들은 탐색할 필요가 없다.
4. 주어진 수들을 중간값(mid)으로 나눠, 몫들의 총 합(pieces)을 구한다.
5. ⓸번에서 구한 몫들의 합(pieces)이 필요한 랜선의 수(n)보다 크거나 같다면
6. 중간값(mid)을 기준으로 이전 값들은 탐색할 필요가 없어지므로 최소값(min)을 중간값에 1을 더한 값으로 변경한다.
7. 문제에서 구하고자 하는 것은 ‘만들 수 있는 최대 랜선의 길이’ 이므로 answer 변수를 활용해 최대값을 구해준다.
8. ⑥번과 반대로, ⓸번에서 구한 몫들의 합(pieces)이 필요한 랜선의 수(n)보다 작다면 조건에 만족하지 않기 때문에, 중간값(mid)을 기준으로 이후 값들을 탐색할 필요가 없어진다. 즉, 최대값(max)을 중간값에 1을 뺀 값으로 변경한다.
9. 최종적으로 answer 는 ‘만들 수 있는 최대 랜선의 길이’를 갖게된다.