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

보석상자

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

<코드>

#include <stdio.h>
long long j[300010] = {};
 
int main(void){
 
    long long  N, M;
    long long result=1000000000;
    long long max = 0;
    scanf("%lld %lld", &N, &M);
 
    for (int i = 0; i < M; i++){
        scanf("%lld", &j[i]);
        if (max < j[i])
            max = j[i];
    }
 
    long long left = 1, right = max;
    
    while (left <= right){
        long long mid = (left + right) / 2;
        long long tempT = 0;
        
        for (int i = 0; i < M; i++)
        {
            tempT += j[i] / mid;
            if (j[i]%mid != 0)
                tempT++;
        }
 
        if (tempT <= N){
            right = mid - 1;
            if (mid<result)
            result = mid;
        }
        else
            left = mid + 1;
 
    }
 
    printf("%lld\n", result);
 
}

<문제 푼 요령>

1. 이 문제는 정답을 유추해서 문제에 대입해서 정답을 판별하는데 이 방법을 이분탐색으로 한다.

2. 이 문제에서는 질투심이 가장 많이 가지고 있는 보석의 수 이므로 정답을 판별하는 경우는 모든 학생이 가장 많은 숫자의 보석을 가졌다고 가정을 하고 판별하면 된다.

3. 판별 방법은 각 보석에 대해서 우리가 유추한 정답으로 나누었을 때의 값을 더하고 이 더한 값이 만약 학생의 수보다 많다면 현재의 학생으로는 만들 수 없기 때문에 정답이 아닌것이다. 즉 그렇기에 반대의 경우는 정답이 되는 것이다.

4. 이 정답중 가장 낮은 값을 정답으로 출력하면 된다.