[백준 16401번] [이분 탐색] 과자 나눠주기

문제를 잘 보면 나눠줄 수 있는 "최대" 길이이므로

만족하는 숫자들의 범위 중 최댓값을 출력해주는 것이다.

 

따라서 이분탐색의 upper_bound를 활용해주면 된다.

 

Upper_bound의 대략적인 skeleton code는 다음과 같다.

// Upper_bound (이분탐색에서의 상계를 구하는 방법)

int start = 0;
int end = vector_container.size();

while (start < end){
    mid = (start + end) / 2;
    
    if(card[mid] <= compare_value){
        start = mid + 1;
    }
    
    else{
        end = mid;
    }
}

이 문제는 아얘 만족하는 숫자가 존재하지 않을 수 있으므로 이 경우에는 index가 start쪽으로 이동하게 되는데

문제는 중간에 mid가 0이 되는 순간이 발생하게 되어서 DivisonByZero가 발생할 수 있다.

이 경우만 따로 Exception handling해주면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
typedef long long ll;

using namespace std;

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    ll M, N;
    cin >> M >> N;

    vector<ll> data_store;

    for(int i = 0; i < N; i++){
        ll temp;
        cin >> temp;
        data_store.push_back(temp);
    }

    sort(data_store.begin(), data_store.end(), greater<ll>());

    ll start = 0;
    ll end = 10000000000000008LL;

    while(start < end){
        ll mid = (start + end) / 2;
        ll check_num = 0;

        if(mid == 0) break;

        for(int i = 0; i < N; i++){
            check_num += data_store[i] / mid;
        }

        // 덜 짤린 것(길이를 줄여야함)
        if(check_num < M){
            end = mid;
        }
        else{
            start = mid + 1;
        }
    }

    if(start != end) cout << 0 << "\n";
    else cout << end - 1 << "\n";
    return 0;
}