https://www.acmicpc.net/problem/16401
입력받은 과자의 길이 중 최대값을 max라고 하면, 조카에게 줄 수 있는 막대 과자의 길이의 범위는 0~max이다.
이 범위에서 이분탐색을 실행하여 답을 찾았다.
현재 탐색하고 있는 과자 길이를 mid라고 하면,
입력받은 n개의 과자 길이를 각각 mid로 나눈 몫의 총합이 과자를 받을 조카의 수 m보다 크거나 같을 때 mid는 갱신된다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int m, n;
vector<int> snack;
int binarySearch() {
int start = 1;
int end = snack[n-1];
int ans = 0;
while(start <= end) {
int mid = (start+end)/2;
int cnt = 0;
for(int i=0; i<n; i++) {
cnt += snack[i] / mid;
}
if(cnt >= m) {
ans = mid;
start = mid+1;
}
else {
end = mid-1;
}
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> m >> n;
snack.resize(n);
for(int i=0; i<n; i++) cin >> snack[i];
sort(snack.begin(), snack.end());
cout << binarySearch();
return 0;
}