https://www.acmicpc.net/problem/1654
백준에 있는 이진탐색 문제입니다.

새벽에 끙끙대다가 놓친 부분이 많아서 기록합니다.

문제

전선 n개의 길이와 목표 개수를 입력받습니다.
목표 개수를 만들기 위해 전선을 특정 길이로 자를 때, 개수를 만족하는 특정 길이 중 가장 큰 길이를 구하는 문제입니다.

오답 코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "../input.txt";

let [firstLine, ...input] = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n");
let [k, n] = firstLine.split(" ").map(Number);
n = Number(n);
input = input.map(Number);

console.log(solution(input, n));

function solution(input, n) {
  let left = 0;
  let right = Math.min(...input);
  let mid = Math.floor(right / 2);

  while (left < mid) {
    let cut = input.map((number) => Math.floor(number / mid));
    const result = cut.reduce((acc, element) => acc + element, 0);
    if (result < n) {
      right = mid;
    } else {
      left = mid;
    }
    mid = Math.floor((right + left) / 2);
  }
  return left;
}

예시를 보고 떠올린 방법이
공통적으로 자르려면 입력받은 선의 길이 중 가장 짧은 선을 최대로 잡아야 한다고 생각했습니다.
이 부분이 오답의 원인1이었고, 이진 탐색코드를 미숙하게 작성한게 원인2입니다.
그리고 가장 큰 길이를 찾아야 한다는 조건도 있었는데 이 부분을 놓친게 원인3입니다.

정답 코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "../input.txt";

let [firstLine, ...input] = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n");
let [k, n] = firstLine.split(" ").map(Number);
n = Number(n);
input = input.map(Number);

console.log(solution(input, n));

function solution(input, n) {
  let left = 1;
  let right = Math.max(...input);
  let max = 0;

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

    const count = input
      .map((number) => Math.floor(number / mid))
      .reduce((acc, number) => acc + number, 0);

    if (count >= n) {
      max = Math.max(max, mid);
      left = mid + 1;
      continue;
    }
    right = mid - 1;
  }
  return max;
}

전선을 반드시 1개이상씩 되어야 할 필요는 없습니다.
따라서 전선의 길이중 가장 짧은 길이를 최대로 잡는 것은 잘못된 생각입니다.
가장 긴 길이까지를 범위로 잡습니다.

이진 탐색 코드를 수정했습니다.

문제에서 n개를 목표로 할 때, n개 이상이 만들어져도 목표에 성공한것이라고 했으니 해당 조건일 때 최대 길이를 저장합니다.

정리

원인1, 원인3은 문제를 제대로 이해하지 못해 생긴 원인입니다.
문제의 조건이나 상황을 다시금 생각해야겠습니다.

원인2는 이진탐색을 코드로 한번에 구현하지 못했습니다.
개념 정리와 코드를 다시 작성해봐야겠습니다.