[Algorithm] Baekjoon 13397번 : 구간 나누기 2

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

13397번: 구간 나누기 2

int n, m;
int arr[5000] = { 0 };
 
bool check(int mid)
{
    int minNum = 0x3f3f3f3f;
    int maxNum = 0;
    int count = 1;
 
    for (int i = 0; i < n; ++i)
    {
        minNum = min(minNum, arr[i]);
        maxNum = max(maxNum, arr[i]);
 
        if (maxNum - minNum > mid)
        {
            ++count;
            minNum = arr[i];
            maxNum = arr[i];
        }
    }
 
    return count <= m;
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
    }
 
    int right = 10001;
    int left = 0;
    int answer = 0x3f3f3f3f;
 
    while (left <= right)
    {
        int mid = (left + right) / 2;
 
        if (check(mid))
        {
            answer = min(answer, mid);
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }
 
    cout << answer;
}

완전탐색문제인줄 알았는데, 시간복잡도가 심상치않아서 어떻게 풀어야할지 고민하다가 풀이법을 참고했다.

이분탐색..이였는데 사실 관련문제를 안푼지 오래되서 그런가 전혀 연관시키지 못했다.

정답률이 굉장히 높길래 엄청 쉽게 생각해서 그런가...

 

mid값을 문제의 정답으로 기준삼고, 실제로 배열에서 m개이하의 구간으로 mid값을 만들 수 있는지 검사한다.

배열 처음부터 최소값,최대값을 업데이트하면서 만약 최대값-최소값이 mid를 넘어서는 순간, 새로운 구간을 만들어서 넘긴다. 반드시 mid값을 만들기 위해서 발악을 한다고 생각하면 된다.

새로운 구간을 추가하다가 m개를 초과할 경우 바로 false를 리턴한다. 즉 절대로 m개이하의 구간으로 mid값을 못만든다고 판단이 되는것이다.