[BaekJoon][2792] 보석 상자

BAEKJOON ONLINE JUDGE

2792 보석 상자

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

보석을 받지 못하는 학생도 있다 -> 보석은 꼭 배분해야 한다. 라고 해석

최대값을 지정해 놓고 그 이하의 개수로 분배를 할 때 받는 학생의 수를 세서

분배를 위해 필요한 학생의 수가 존재하는 학생의 수보다 많으면 -> 보석을 전부 분배할 수 없다 -> 최대값을 늘린다.

분배를 위해 필요한 학생의 수가 존재하는 학생의 수보다 작으면 -> 보석을 전부 분배할 수 있다 -> 최대값을 줄일 수 있다.

=> 이분탐색

#include <stdio.h>
 
int n, m;
int stone[300000];
 
int ispossible(int num)
{
    int max = 0;
    int i;
    int cnt = 0;
    for (i = 0; i < m; i++) {
        cnt += (stone[i] - 1) / num + 1;
        if (cnt > n)    return 0;
    }
    return 1;
}
 
int bsearch()
{
    int i;
    int s = 1, e = 1e9;
    int middle;
    int temp;
 
    while (s <= e) {
        middle = (s + e) / 2;
 
        if (!ispossible(middle))    s = middle + 1;
        else                        e = middle - 1;
    }
 
    return e + 1;
}
 
int main()
{
    int i;
 
    scanf("%d %d", &n, &m);
 
    for (i = 0; i < m; i++) {
        scanf("%d", &stone[i]);
    }
 
    printf("%d\n", bsearch());
 
    return 0;
}