[BOJ/백준][Gold4] 13397 : 구간 나누기 2 (C++)

https://www.acmicpc.net/problem/13397

13397번: 구간 나누기 2

 

[난이도] Gold4
[유형] 이분 탐색

[풀이]
구간을 몇개로 나누어야 하는지, 어디를 기준으로 나누어야 하는지를 찾으려고 하면 N 제한이 5000이므로
무리가 있습니다.

이런 방법들 대신에 최종적으로 구해야하는 답인 "구간의 점수의 최댓값의 최솟값"에서 "구간의 점수의 최댓값" 을 어떤 수 m으로 고정해놓고 구간을 나눠보는 방식을 사용할 수 있습니다.

어떤 구간의 점수도 m 이상이 되도록 구간을 나누었을 때, 총 구간의 개수가 M 이하라면 이 m의 값은 정답이 될수도 있는 값이지만 최솟값은 아닙니다. 이 m의 값을 조금씩 줄여가면서 답이 될 수 있는지 확인해보는 이분탐색을 이용하면
시간내에 최적의 m 값을 찾을 수 있습니다.

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N,M,a[5001];
bool check(int m){
    int cnt=0;
    int minv=a[0],maxv=a[0];
    for(int i=0;i<=N;i++){
        minv=min(minv,a[i]);
        maxv=max(maxv,a[i]);

        int diff = maxv-minv;
        if(diff<=m) continue;
        cnt++;

        minv=maxv=a[i];
    }
    return cnt<=M;
}
int sol(){
    int lo=-1,hi=10000;
    while(lo+1<hi){
        int mid=(lo+hi)/2;
        if(check(mid)) hi=mid;
        else lo=mid;
    }
    return hi;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    a[N]=1e5;
    printf("%d",sol());
}

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/13397.cpp