BOJ 16401, 과자 나눠주기

문제

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

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

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

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

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

입력

첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에 과자 N개의 길이 L1, L2, …, LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, …, LN ≤ 1,000,000,000) 를 만족한다.

출력

첫째 줄에 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 출력한다.

단, 모든 조카에게 같은 길이의 막대과자를 나눠줄 수 없다면, 0을 출력한다.

예제 입력 1

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

예제 출력 1

예제 입력 2

4 3
10 10 15

예제 출력 2

내가 한 생각들

처음 접근은 이진 탐색 시 mid를 과자 N 개의 길이 수열 A의 원소 인덱스로 써야겠다고 생각함.
이 경우 mid로 선택된 과자 길이 Lmid보다 작은 길이의 과자는 Lmid로 나눠질 수 없기 때문에 제외시킬 수 있겠다고 생각함. 이러면 이진 탐색 시 low와 high는 각각 과자 길이에 대해 정렬된 수열 A의 A[0], A[N - 1]로 초기화할 수 있다고 생각함.
여기서 간과한 점은 A[mid] 로 선택한 과자 길이 Lmid라고 무조건 Lmid로 나눠야한다는 것은 아니였고, Lmid보다 작은 값부터 나눠보기 시작할 수 있다는 것을 몰랐음.
mid를 단순히 M명의 사람에게 나눠줄 수 있는 과자의 최대 길이 X로 생각하고, 여기에 이 X 보다 길이가 작은 여러 과자를 합쳐서 만들 수 없다는 점을 다시 한 번 생각해봄.

내 구현

#include <algorithm>
#include <iostream>
#define IO std::cin.tie(NULL), std::ios_base::sync_with_stdio(false)

#define MAX 1000000

int M, N;
int A[MAX];

void solve() {
  int l = 1, h = A[N - 1], m, x, result = 0;

  while (l <= h) {
    m = l + (h - l) / 2;
    x = 0;
    for (int i = 0; i < N; i++) {
      x += A[i] / m;
    }

    if (M <= x) {
      result = m;
      l = m + 1;
    } else {
      h = m - 1;
    }
  }

  std::cout << result;
}

void initial() {
  std::cin >> M >> N;

  for (int i = 0; i < N; i++) {
    std::cin >> A[i];
  }

  std::sort(A, A + N);
}

int main() {
  IO;
  initial();
  solve();
  return 0;
}