2343 기타레슨 (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;
    high = INF / m;
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
        if (arr[i] > low)
            low = arr[i];
    }
 
    int tmp=1,mid;
    while (low<= high) {                
        int sum = 0;
        mid = (low + high) / 2;
        for (int i = 0; i < n; i++) {
            if (sum + arr[i] <= mid) {
                sum +=arr[i];            
            }
            else {
                sum = arr[i];
                tmp++;
            }
            
        }
 
        if (tmp <= m) {
            high = mid-1;
        }
        else {
            low = mid+1;
        }
        tmp = 1;
    }
    printf("%d", low);
}