[C++] 백준 16401번 과자 나눠주기

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;
}