[백준 13397] 구간 나누기 2 C++

www.acmicpc.net/problem/13397

13397번: 구간 나누기 2

 

m개 이하의 구간을 나누어서 각 구간마다의 최댓값 최솟값을 뺀 값 중에서,

최댓값이 나올 수 있는 모든 경우의 수에서

최댓값 중에서 최솟값을 구하는 문제입니다.

구해야하는 값이 조금 복잡하다고 느낄 수 있습니다. 각 구간마다의 최댓값 최소값을 뺀 값 중에서 최댓값을 구하는건 알겠지만,

그러한 구간의 경우수가 정말 많기 때문에, 각 경우의 수마다의 최댓값 중에서 최솟값을 구하는 문제입니다.

 

구간의 경우의 수를 나누어야하는데, 브루트 포스로 나누려고 생각했을 때

예외처리 하기가 복잡해지고 경우의 입력 n에 따라서 기하급수적으로 많아 질것이라고 생각했습니다.

 

따라서, 이분탐색을 이용해서 목표하고자하는 최종 값인 최댓값중의 최솟값을 mid 파라미터로 설정하면서,

mid에 따라서, mid보다 큰 최댓값을 가지는 구간들을 카운트해서 m 개수 보다 작을 때 mid의 최솟값을 구하면 됩니다. 

 

코드로 나누어서 설명을 하자면,

for (int i = 0; i < n; i++) cin >> arr[i]; // 입력

    int right = *max_element(arr.begin(), arr.end()); // 입력받은 배열 중 최댓값을 right값으로 설정
    int left = 0; // 최솟값 0
    int res = right;

    while(left <= right){ // 적절한 값을 찾기 위해서 이분탐색으로 하나씩 돌려본다.
        int mid = (left + right) / 2;

        if (cal(arr, mid)){
            if (res > mid) res = mid; // 최솟값 업데이트해주기 // cal함수를 통해서 조건에 맞는 m개 이하의 구간을 찾았을 때, mid의 최솟값을 업데이트해준다.
            right = mid - 1; // mid를 더 작게 만들어보기
        } else left = mid + 1; // mid를 더 크게 만들어보기
    }

입력을 받은 뒤,

left(최솟값)은 0, right(최댓값)은 배열 중에서 가장 큰 원소를 대입합니다.

 

이분탐색을 통해서 (left + right) / 2인 mid (구간 경우의 수 (최댓값-최솟값)의 최댓값 중에서 최솟값 = 목표하는 값)을 설정한 뒤,

그 값보다 이상인 값을 찾으면 됩니다.(해당 구간을 임의로 나누어서 m개 이하로 만들면 됩니다_)

 

m개 이하의 mid이상이 만족되는 구간을 찾는 코드는

bool cal(vector<int> &arr, int mid){
    vector<int> temp;

    int cnt = 1;
    int minV, maxV;

    minV = arr[0];
    maxV = arr[0];

    for (int i = 1; i < n; i++){
        
        if (arr[i] < minV) minV = arr[i];
        if (arr[i] > maxV) maxV = arr[i];

        if ((maxV - minV) > mid){ // 차이가 목표하는 mid보다 크면 구간 카운트 + 1
            cnt++;
            minV = arr[i];
            maxV = arr[i];
        }
    }
    return cnt <= m;
}

입니다.

 

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m;

bool cal(vector<int> &arr, int mid){
    vector<int> temp;

    int cnt = 1;
    int minV, maxV;

    minV = arr[0];
    maxV = arr[0];

    for (int i = 1; i < n; i++){
        
        if (arr[i] < minV) minV = arr[i];
        if (arr[i] > maxV) maxV = arr[i];

        if ((maxV - minV) > mid){
            cnt++;
            minV = arr[i];
            maxV = arr[i];
        }
    }
    return cnt <= m;
}
void solution(){

    cin >> n >> m;
    vector<int> arr(n);

    for (int i = 0; i < n; i++) cin >> arr[i];

    int right = *max_element(arr.begin(), arr.end());
    int left = 0;
    int res = right;

    while(left <= right){ // 적절한 값을 찾기 위해서 이분탐색으로 하나씩 돌려본다.
        int mid = (left + right) / 2;

        if (cal(arr, mid)){
            if (res > mid) res = mid; // 최솟값 업데이트해주기
            right = mid - 1;
        } else left = mid + 1;
    }


    cout << res << '\n';    

}
int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solution();

    return 0;
}