CSES 2. Array Division (1085)

출처: https://cses.fi/problemset/task/1085

---

문제 설명

You are given an array containing n positive integers.

Your task is to divide the array into k subarrays so that the maximum sum in a subarray is as small as possible.

입력 

The first input line contains two integers n and k: the size of the array and the number of subarrays in the division.

The next line contains n integers x_1,x_2,…,x_n: the contents of the array.

출력  

Print one integer: the maximum sum in a subarray in the optimal division.

입력 예

5 3
2 4 7 3 5

출력 예

8

Explanation: An optimal division is [2,4],[7],[3,5] where the sums of the subarrays are 6,7,8. The largest sum is the last sum 8.

제약조건

• 1 <= n <= 2x10^5 
• 1 <= k <= n 
• 1 <= x_i <= 10^9

---

문제 풀이 

입력받은 수열의 합과 최대값을 기록한다.

수열을 가장 작은 크기로 분할하는 것은 모두 1개씩으로 분할 하는 것이다. 이때는 수열 내 원소의 최대값을 출력한다. 가장 크게 분할하면 전체를 하나로 분할하는 경우이므로, 수열의 합을 출력한다.

나머지 분할에서 나오는 값들은 이 두 값의 사이에 존재하게 되므로, high/low로 생각하고 중간값들로 분할 가능한지 확인해서, 가능한 경우에서 최소값을 출력한다.

프로그램 내용

...
bool possible(const vector<long long>& arr, int k, long long x)
{
    int div = 1;
    long long sum = 0;
    int i = 0;

    while(i < (int)arr.size())
        if(sum + arr[i] <= x)
            sum += arr[i];
            ++i;
        else
            ++div;
            sum = 0;
    return div <= k;
};

...
	vector <long long> num_arr(nNum);

    long arr_sum=0;
    long arr_max=0;

    for(int idx=0; idx < nNum; ++idx)
        long temp;
        num_arr[idx] = temp;
        arr_sum += temp;
        arr_max = max(arr_max, temp);

    if ( tSub == 1)
        cout << arr_sum <<endl;

	long long low = arr_max;
    long long high = arr_sum;

    while(low < high)
        long long mid = (low+high+1) / 2ll;

		if(possible(num_arr, tSub, mid))
			if(!possible(num_arr, tSub, mid-1))
				cout << mid;
			high = mid - 1;
		else
			low = mid + 1;
...

 

Sorting and Searching ( link )