백준 1654번

QUESTION LINK

주어진 전선들 중 요구하는 개수의 조각들이 나올 수 있도록 나누기를 반복해야하는 문제였습니다. 가장 먼저 고민했던 것은 ‘원하는 값을 구하기 위해서 주어진 값들에 대해 반복적인 나누기를 해야하는지’ 였는데 이 부분은 개수를 비교하기 위해서는 필수적으로 거쳐야하는 과정이라 어쩔 수 없다는 것을 파악했습니다.

다음으로 고민했던 것은 이분 탐색을 할 때, ‘어떻게 해야 만족되는 값들 중 가장 큰 값에 접근할 수 있는지’ 였습니다. 처음에는 최대값으로 현재 주어진 값들 중 가장 큰 값을 설정하고, while문을 통한 이분 탐색으로 만족되는 값을 구하고, 이후 하나씩 올라가며 최대값을 구하려고 하였으나, 이로 인해 시간 초과가 나왔습니다.

이후, 이분 탐색에 대해 알게 된 것이 원하는 결과가 나올 때까지 Upper Bound를 이용해서 값을 구해주면 된다는 것이었습니다. 여기서 Upper Bound는 특정 조건을 만족하는 값의 다음 값을 보여주게 되는 것인데, 이를 이용해서 원하는 값이 나오도록 할 수 있었습니다.

구현을 위해, 초기값으로는 최소값(min)과 최대값(max)을 설정하게 되는데, 여기서 길이를 구하는 문제이기 때문에 최소값은 1로 처음에 설정을 해주어야 합니다. 이렇게 진행하지 않을 시, 이후 이분 탐색에서 중간값을 구할 때 중간값이 0이 나올 수도 있다는 문제가 생겨, 이 부분에 대한 처리가 꼭 필요합니다.

const [counts, ...linesString] = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n");
const [K, N] = counts.split(" ").map(Number);
const lines = linesString.map(Number);

let min = 1;
// 최소값으로 0이 아닌 1로 설정
let max = Math.max(...lines);
// 최대값은 현재 주어진 값들 중 가장 큰 값

이후, while문을 통한 반복을 하게 되는데, 여기서 조건 설정에 대한 어려움이 있었습니다. 앞서 말한 Upper Bound를 하기 위해서는 순회 시 구해진 값이 요구되는 값과 일치될 때 만족시킨 중간값(mid)보다 더 큰 값으로 최소값을 설정해 반복해야 Upper Bound를 통해 요구되는 값보다 하나 더 큰 값을 얻을 수 있게 됩니다.

하지만, 이렇게 진행을 하고 나서, 마지막에 while문을 종료시켜야 하는데 이 때 적용할 조건으로 기존에는 최소값이 최대값보다 작은 상황(min < max)에 대해서만 진행하도록 했습니다. 이럴 경우 틀렸다는 결과가 나오게 되는데 이는 max값이 1이 될 수도 있다는 것을 고려하지 못하기 때문입니다. max가 1인 상황에서도 해당 순회가 한 번은 돌아가고 이에 따른 결과가 나와야 하기 때문에, min ≤ max로 조건을 설정해야 합니다.

그리고 이렇게 조건을 진행할 경우, 기존의 Upper Bound와 달리 한 번 더 max값에 대한 처리가 이루어지기 때문에 추가적인 -1 조치는 필요가 없어지게 됩니다.

while (min <= max) {
  const mid = Math.floor((min + max) / 2);
  const count = lines.reduce((prev, next) => {
    return prev + Math.floor(next / mid);
  }, 0);
  // 모든 같은 길이의 전선들의 합
  if (count >= N) {
    // 값이 일치하더라도 최대까지 진행해 나가야 함
    min = mid + 1;
  } else {
    max = mid - 1;
  }
}

console.log(max);

GITHUB  EMAIL