[ BOJ / C++ ] 13397번 구간 나누기 2

이번 문제는 이분탐색을 통해 해결하는 문제였다. 이분탐색의 범위에 대해서 고민을 많이 했던 것 같다. 이분탐색의 범위는 0과 배열의 최대값으로 하였다.

• 배열을 돌며 해당 인덱스에서의 최대값-최소값의 값이 mid보다 크다면 cnt를 증가시켜주고, cnt가 m보다 작거나 같으면 true, 아니라면 false를 반환하는 bool형 함수 Check를 작성한다. 이때, cnt가 증가하면 그 인덱스를 저장하고, 그 다음에 돌때는 저장된 인덱스 이후부터 돌도록 한다.(구간을 나누는 것을 구현)
• 이분탐색 시 front에 0을, back에 배열의 최대값을 넣고, while문의 조건은 front<=back으로 둔다. (모든 경우 확인)
• 매 반복마다 Check함수의 반환값이 true이면, result에 mid를 넣어준다.
• result에 결과가 저장된다.

#include <iostream>
#include <algorithm>
#define MAX 5001
using namespace std;

int n, m;
int arr[MAX];

void Input(){
    cin>>n>>m;
    for(int i=0; i<n; i++){
        cin>>arr[i];
    }
}

bool Check(int mid){
    int cnt=1;
    int mini=10001;
    int maxi=0;
    int idx=-1;
    for (int i=idx+1; i<n; i++){
        mini=min(mini, arr[i]);
        maxi=max(maxi, arr[i]);
        if(maxi-mini>mid){
            cnt++;
            mini=arr[i];
            maxi=arr[i];
            idx=i;
        }
    }
    return cnt<=m;
}

int Solution(){
    int big=0;
    for(int i=0; i<n; i++){
        big=max(big, arr[i]);
    }
    int result=0;
    int front=0;
    int back=big;
    while(front<=back){
        int mid=(front+back)/2;
        if(Check(mid)){
            result=mid;
            back=mid-1;
        }
        else
            front=mid+1;
    }
    return result;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    cout<<Solution()<<endl;
    return 0;
}