백준 2792 보석 상자

https://www.acmicpc.net/problem/2792

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

using namespace std;

vector<int> color;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m;

    cin >> n >> m;

    color.resize(m);


    for (int i = 0; i < m; i++) {
        cin >> color[i];
    }

    sort(color.begin(), color.end());

    int l = 1;
    int r = color.back();
    int ans;

    while (l <= r) {

        //질투심
        int mid = (l + r) / 2;

        //학생의 수
        int cnt = 0;
        for (int i = 0; i < m; i++) {
            cnt += color[i] / mid;
            if(color[i]%mid!=0) {
                cnt++;
            }
        }

        if (cnt <= n) {
            r = mid - 1;
            ans = mid;
        } else {
            l = mid + 1;
        }

    }

    cout << ans;

    return 0;
}

 마찬가지로 이분탐색 문제이다. 보석을 학생들에게 나누어주었을 때 질투심의 최솟값을 구하면 된다.

    int l = 1;
    int r = color.back();
    int ans;

 질투심은 가장 많은 보석을 가져간 학생의 보석의 수이고, 보석을 받지 못하는 사람이 있을 수 있으므로 질투심은 1부터 색이 같은 보석의 최대 개수 중 하나이다. 이 범위 내에서 이분 탐색을 실행한다.

 while (l <= r) {

        //질투심
        int mid = (l + r) / 2;

        //학생의 수
        int cnt = 0;
        for (int i = 0; i < m; i++) {
            cnt += color[i] / mid;
            if(color[i]%mid!=0) {
                cnt++;
            }
        }

        if (cnt <= n) {
            r = mid - 1;
            ans = mid;
        } else {
            l = mid + 1;
        }

    }

 질투심은 보석의 개수의 최댓값이므로 보석을 해당 개수만큼 나누면 학생의 수가 구해진다. 만약 나누어 떨어지지 않을 경우 나머지 한 사람에게 나머지 보석을 나누어야 하므로 학생이 한 명 늘어난다.

 이후 나누어야 할 학생이 n 이하일 경우 각 학생에게 보석을 적게 주어야 받을 학생이 늘어나므로 l~mid-1에 대해 이분 탐색을 수행하고, 반대의 경우 mid+1~r에 대해 수행한다. 연산 후 결과를 출력하면 답을 구할 수 있다.