[백준 2792번] [이분 탐색] 보석 상자

잘 생각해보면, 특정한 수를 나누고 몫과 나머지와 관련있다는 사실까지는 쉽게 파악할 수 있다.

 

다만, 해당하는 숫자를 판단하기 위해서 10e9 숫자를 판단해야하는데 이 부분은 이분탐색으로 해결할 수 있음을 알 수 있다.

 

추가적으로 만족하는 상황 중에 가장 작은 숫자를 찾는 것이므로 lower_bound를 물어보는 것이다.

따라서 lower_bound binary search를 진행해주면 된다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
typedef long long ll;

int main(void){
    fastio;
    ll n, m;
    cin >> n >> m;
    vector<ll> data;
    
    for(int i = 0; i < m; i++){
        ll temp;
        cin >> temp;
        data.push_back(temp);
    }

    ll start = 1;
    ll end = 1000000000;

    while(start < end){
        ll mid = (start + end) / 2;
        ll count = 0;
        for(int i = 0; i < m; i++){
            if(data[i] % mid == 0){
                count += data[i] / mid;
            }
            else count += (data[i] / mid) + 1;
        }
        if(count > n){
            start = mid + 1;
        }
        else end = mid;
    }

    cout << start << "\n";
    return 0;
}