[13397] 구간 나누기2

문제 링크

주어진 배열을 M개로 나누었을 때 구간의 점수들의 최댓값의 최솟값을 구하는 문제이다.

예를 들어, 배열이 [1, 5, 4, 6, 2, 1, 3, 7] 이고, M = 3인 경우가 있다.

이때, [1, 5], [4, 6, 2], [1, 3, 7]로 구간을 나누면 각 구간의 점수는 4, 4, 6점이 된다. 이때, 최댓값은 6점이다.

만약, [1, 5, 4], [6, 2, 1], [3, 7]로 구간을 나누었다면, 각 구간의 점수는 4, 5, 4점이 되고, 이때 최댓값은 5점이 된다.

 

이 문제를 풀기 위해 아래의 방법으로 접근했다.

• 먼저 최솟값을 설정하고, 이 최솟값을 만족하기 위해 배열이 몇 개로 나누어지는지 구한다.
• 나누어진 배열의 갯수가 M보다 크다면 목표 최솟값을 높이고, M보다 작다면 목표 최솟값을 낮춘다.

주어진 배열을 M개로 나누어가며 최솟값을 구하지 않고, 목표 최솟값을 변경해가며 배열이 M개로 나누어지는 경우를 탐색하는 것이다.

코드는 아래와 같다.

 

​x
#include <cstdio>
#include <climits>
using namespace std;
int main() {
    int N, M;
    scanf("%d %d", &N, &M);
    int ARR[5000];
    for (int i = 0; i < N; i++) scanf("%d", &ARR[i]);
​
    int left = 0, right = INT_MAX;
    while (left <= right)
    {
        int c = (left + right) / 2;
        int curr_m = 1;
        int max_val = ARR[0], min_val = ARR[0], score = 0;
        for (int i = 1; i < N; i++)
        {
            if (max_val < ARR[i]) max_val = ARR[i];
            if (min_val > ARR[i]) min_val = ARR[i];
            if (max_val - min_val > c)
            {
                min_val = ARR[i];
                max_val = ARR[i];
                curr_m++;
            }
        }
​
        if (curr_m > M) left = c + 1;
        else right = c - 1;
    }
    printf("%d\n", left);
    return 0;
}