6236 용돈관리 (PS)

#include <stdio.h>
#define INF 1e9
 
int arr[100001] = { 0 };
 
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
 
    int low = 0, high = INF / m;
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
        if (low < arr[i])
            low = arr[i];
    }
 
    while (low <= high) {
        int mid = (low + high) / 2;
        int sum = 0, tmp=0;
        for (int i = 0; i < n; i++) {
            if (sum + arr[i] > mid) {
                sum = 0;
                tmp++;
            }
            sum += arr[i];
        }
        if (sum != 0)    
            tmp++;
        
        if (tmp > m)
            low = mid + 1;
        else
            high = mid - 1;
    }
 
    printf("%d", low);
}