[백준][C++] 2792: 보석 상자

문제

풀이

이분 탐색을 사용한다.

• 나눠줄 보석의 수를 이분 탐색하여 진행한다. 
• 보석은 최소 1개 나눠줄 수 있고, 최대 가장 수가 많은 보석의 수만큼 나눠줄 수 있다. 
• 보석마다 mid만큼 나눠준다면 (현재 보석의 수 / mid)만큼의 학생에게 나눠줄 수 있으며, 나눠준 후 보석이 남았다면 1명의 학생에게 추가적으로 나눠줄 수 있다.
• mid만큼 보석을 나눠줬을 때, 나눠줄 수 있는 학새의 수와 N을 비교하여 다음 이분 탐색의 범위를 새로 한다. 
• 질투심은 mid만큼 나눠줬을 때의 mid가 해당 검사에서의 최댓값이다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> jewels;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(nullptr);

    int N, M;
    cin >> N >> M;

    for (int i = 0; i < M; ++i)
    {
        int temp;
        cin >> temp;
        jewels.push_back(temp);
    }
    sort(jewels.begin(), jewels.end());

    // 보석은 최소 1개 나눠 줄 수 있고
    // 최대로는 수가 가장 많은 보석만큼 나눠줄 수 있다. 
    int start = 1;
    int end = jewels[M - 1];
    int answer = 0;
    while (start <= end)
    {
        int mid = (start + end) / 2;

        // 보석을 mid만큼 나눠줄 때, current의 학생에게 나눠줄 수 있다. 
        int current = 0;
        for (int i = 0; i < M; ++i)
        {
            // mid만큼 나눠준다면 (현재 보석의 수 / mid)만큼의 학생에게 나눠줄 수 있으며
            // 나머지가 있다면 한명의 학생에게 추가로 나눠줄 수 있다.
            current += jewels[i] / mid;

            if (jewels[i] % mid != 0)
            {
                current++;
            }
        }

        // mid만큼 나눠줬을 때, N보다 적다면 나눠줄 보석의 수를 줄인다.
        if (current <= N)
        {
            answer = mid;
            end = mid - 1;
        }
        else
        {
            start = mid + 1;
        }
    }

    cout << answer;

    return 0;
}