[2792번] 보석 상자

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 이분 탐색

이분 탐색을 이용해 문제를 해결 할 수 있다.

end 부분을 보석 종류 중 개수가 가장 많은 값으로 잡고 mid를 질투심으로 잡아 이분탐색마다 보석을 나눠줘보고

사람수가 n보다 크면 질투심을 늘리고 그게 아니면 질투심을 -1해준다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <cmath>
 
#define max(a, b)(a > b ? a : b)
#define min(a, b)(a < b ? a : b)
 
using namespace std;
 
int arr[300002];
 
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
 
    int total = 0;
    int start = 0, end = 0;
    for (int i = 0; i < m; i++)
    {
        scanf("%d", &arr[i]);
        end = max(end, arr[i]);
        total += arr[i];
    }
 
    int ans = 987654213;
    while (start <= end)
    {
        int mid = (start + end) / 2;
 
        int people = 0;
        for (int i = 0; i < m; i++)
        {
            int div = arr[i] / mid;
            int rem = arr[i] % mid;
 
            if (!rem)
                people += div;
            else
                people += div + 1;
        }
 
        if (people > n)
            start = mid + 1;
        else
        {
            end = mid - 1;
            ans = min(ans, mid);
        }
    }
 
    return !printf("%d", ans);
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>