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

문제

주어진 배열에서 M개 이하의 구간을 만들 때, 각 구간의 값(최댓값과 최솟값)의 최댓값 중 최솟값을 구하는 문제

 

생각

0부터 배열에서 가장 큰 값까지 이분 탐색을 이용해야겠다 생각함

구간의 최댓값-최솟값이 mid보다 크면 cnt값을 늘려서 M보다 큰지 작은지 비교하면 됨

 

문제풀이

1.st=0, en=배열에서 가장 큰 값으로 두고 이분 탐색 시작

2.배열을 돌면서 구간마다 최솟값, 최댓값 갱신해줌

3.만약 최댓값-최솟값이 Mid보다 크다면, cnt++ | 최댓값 = 현재 배열값 / 최솟값 = 현재 배열값으로 초기화해줌 ( 다음 구간으로 넘어갔다고 생각하면 됨 )

4.만약 cnt가 M보다 커진다면 ck = 1 하고 break 해줌

5.만약 cnt가 M보다 크거나 ck == 1 일 경우, st = mid + 1 - 더 큰 값에서 탐색해야함

5-1.만약 cnt가 M과 같거나 작을 경우, result = mid 저장하고 en = mid - 1 - 더 작은 값에서 탐색해야함

6.result 출력 ( 초기값은 배열에서 가장 큰 수 ) - ( 배열의 크기가 1이면 mid값이 설정이 안되기 때문 

 

코드

#include <iostream>
#include <algorithm>
using namespace std;
int N, M, min_N=10000, max_N=0;
int arr[5001];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    for ( int i = 0; i < N; i++ ) {
        cin >> arr[i];
        min_N = min(min_N, arr[i]);
        max_N = max(max_N, arr[i]);
    }

    int st = 0, en = max_N, result=en;
    while ( st <= en ) {
        int mid = ( st + en ) / 2;
        
        int cnt = 1, ck=0;
        int i_s=arr[0], i_e=arr[0];
        for ( int i = 1; i < N; i++ ) {
            i_e = max(i_e, arr[i]);
            i_s = min(i_s, arr[i]);
        
            if ( i_e - i_s > mid ) {
                i_s = arr[i];
                i_e = arr[i];
                cnt++;
            }

            if ( cnt > M ) {
                ck = 1;
                break;
            }
        }

        if ( cnt > M || ck == 1 )
            st = mid + 1;

        else {
            result = mid;
            en = mid - 1;
        }
    }
    cout << result;
}