백준[16401] 과자 나눠주기

문제 설명

문제 링크

http://icpc.me/16401

16401번: 과자 나눠주기

풀이

결정문제로 바꿔 이분 탐색을 하여 풀 수 있다.

m명에게 길이가 n인 과자를 줄 수 있는지 없는지 판단하는 문제로 바꿔, 길이 n을 이분탐색을 돌리면 된다.

이렇게 풀면 O(NlogN)에 풀 수 있다.

코드

#include <cstdio>

int arr[1000006];

int main() {
    int m, n; scanf("%d %d", &m, &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", arr + i);
    }
    int l = 0, r = 1e9, mid;
    while (l + 1 < r) {
        mid = (l + r) >> 1;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += (arr[i] / mid);
        }
        if (sum < m) r = mid;
        else l = mid;
    }
    printf("%d", l);
}