[백준 c++] 2792 보석 상자

문제

https://www.acmicpc.net/problem/2792
M개의 보석을 N명의 아이들에게 나눠주려고 하는데 한 명의 아이가 여러 종류의 보석을 받을 수 없다. (안받거나 한 종류 보석만 받거나)

질투심(가장 많은 보석을 받은 아이가 받은 보석의 개수)의 최소값을 구하라

풀이

특정 범위 내에서 특정값(질투심)을 찾아야하니까 이분탐색을 이용해서 풀 수 있다.
left:1
right: 보석 중 최대값
mid: =(left + right)/2 => 질투심

현재 mid값을 질투심이라고 가정했을 때
질투심에 맞게 보석수를 나눠줄수 있으면 right = mid-1 로 두고 아니면 left = mid +1

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, m;
int main()
{
    cin >> n >> m;
    vector<long long> v(m);
    long long mid, ret, left = 1, right = 0, sum;
    for (int i = 0; i < m; i++)
    {
        cin >> v[i];
        right = max(v[i], right);
    }

    while (left <= right)
    {
        mid = (left + right) / 2;
        sum = 0;
        for (int i = 0; i < m; i++)
        {
            sum += v[i] / mid;
            if (v[i] % mid)
                sum++;
        }
        if (sum <= n)
        {
            right = mid - 1;
            ret = mid;
        }
        else
            left = mid + 1;
    }
    cout << ret << "\n";

    return 0;
}