[BOJ/16401번과자나눠주기] c++ / binary_search

문제

홍익이가 조카들에게 나눠줄 수 있는 과자의 최대 길이를 구하는 문제

-조카들에게 나눠주는 과자의 길이는 모두 같아야 함

-만약 같은 길이로 나누어 줄 수 없을 경우 0을 출력

 

생각

과자의 길이를 이분탐색해야겠다 생각함

 

문제풀이

1.st=1, en=arr[N-1] (제일 긴 과자의 길이)로 두고 이분탐색 시작

2.mid = ( st + en ) / 2

3.arr[i]가 mid보다 크다면 cnt += arr[i] / mid

4-1.만약 cnt >= M 이라면, result = mid; st = mid + 1 - 더 큰 길이에서 탐색해야함

4-2.만약 cnt < M 이라면, en = mid - 1 - 더 작은 길이에서 탐색해야함

5.result 값 출력

 

반례 ) st = 1로 설정하고 해결

3 3
1 2 3

 

코드

#include <iostream>
#include <algorithm>
using namespace std;
int M, N;
long long arr[1000001];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> M >> N;
  for ( int i = 0; i < N; i++ ) cin >> arr[i];
  sort(arr, arr+N);

  long long st = 1, en = arr[N-1], result=0; // 과자의 길이
  while ( st <= en ) {
    long long mid = ( st + en ) / 2;

    int cnt = 0;
    for ( int i = 0; i < N; i++ ) {
      if ( arr[i] >= mid ) 
        cnt += arr[i] / mid;
    }
    if ( cnt >= M ) {
      result = mid;
      st = mid + 1;
    }
    else 
      en = mid - 1;
  }
  cout << result;
}