과자 나눠주기

과자 나눠주기

문제 설명

명절이 되면, 홍익이 집에는 조카들이 놀러 온다. 떼를 쓰는 조카들을 달래기 위해 홍익이는 막대 과자를 하나씩 나눠준다.

조카들이 과자를 먹는 동안은 떼를 쓰지 않기 때문에, 홍익이는 조카들에게 최대한 긴 과자를 나눠주려고 한다.

그런데 나눠준 과자의 길이가 하나라도 다르면 조카끼리 싸움이 일어난다. 따라서 반드시 모든 조카에게 같은 길이의 막대 과자를 나눠주어야 한다.

M명의 조카가 있고 N개의 과자가 있을 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 구하라.

단, 막대 과자는 길이와 상관없이 여러 조각으로 나눠질 수 있지만, 과자를 하나로 합칠 수는 없다. 단, 막대 과자의 길이는 양의 정수여야 한다.

예제 입력

3 10
1 2 3 4 5 6 7 8 9 10

예제 출력

8

---

문제 풀이

const fs = require("fs");
const path = require("path");
const input = fs
  .readFileSync(
    process.platform === "linux"
      ? "/dev/stdin"
      : path.join(__dirname, "input.txt")
  )
  .toString()
  .trim()
  .split("\n");

const solution = (input) => {
  const [M, N] = input[0].split(" ").map(Number);

  const arr = input[1].split(" ").map(Number);

  arr.sort((a, b) => a - b);
  const bis = () => {
    let left = 1;
    let right = arr[arr.length - 1];
    let answer = 0;

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

      let cnt = 0;
      // 과자를 현재 설정한 길이로 나눴을 때 몇개가 나오는 지 계산
      for (let snack of arr) {
        cnt += Math.floor(snack / mid);
      }
      // 만약 나눈 개수가 M보다 크거나 같을 경우 정답 갱신 후 값을 늘려서 더 탐색하기
      if (cnt >= M) {
        left = mid + 1;
        answer = mid;
        // 아니라면 범위 줄이기
      } else {
        right = mid - 1;
      }
    }
    return answer;
  };
  let result = bis();
  console.log(result);
};
solution(input);

아이디어 / 접근법

1. 과자들을 현재 기준으로 잡은 값(mid)로 나눔
2. 그 값들이 M 보다 크거나 같다면 left 값 늘리고 정답 갱신
3. 아니라면 right 값 줄이기

후기

과자를 나눈다는 의미가 좀 명확하게 와닿지 않아서 생각을 좀 했는데 어려운 문제는 아니었음