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

시간 복잡도

• N이 최대 5,000 이므로 이분 탐색을 이용해 $O(logn)$의 시간 복잡도로 해결할 수 있습니다.

문제 접근법

• mid를 구간의 최댓값과 최솟값의 차이로 놓고 이분 탐색을 진행합니다.
• mid가 최소가 되어야 하므로 구간의 최댓값과 최솟값의 차이가 mid보다 크다면 구간을 나눕니다.
• 구간의 개수를 세어줍니다.
• 구간의 개수가 M보다 크다면 정답이 될 수 없으므로 left을 증가시키고
• 구간의 개수가 M보다 작거나 같으면 정답이 될 수 있으므로 right를 감소시키고
• mid값이 최소가 되도록 업데이트합니다.

코드

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>
#include <climits>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>


using namespace std;

using int32 = long;
using int64 = long long;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<int> v(N);

    int l = 0;
    int r = 0;
    int mid = 0;

    for (int i = 0; i < N; i++)
    {
        cin >> v[i];
        if (v[i] > r)
            r = v[i];
    }

    int answer = r;
    while(l<=r)
    {
        mid = (l + r) / 2;

        int cnt = 1;
        int Max = 0;
        int Min = INT_MAX;

        for(int i=0; i<N; i++)
        {
            if (v[i] < Min)
                Min = v[i];
            if (v[i] > Max)
                Max = v[i];

            if(Max-Min > mid)
            {
                cnt++;
                Max = v[i];
                Min = v[i];
            }
        }

        if (cnt <= M)
        {

            if(answer > mid)
            {
                answer = mid;
            }
            r = mid - 1;
        }
        else
        {
            l = mid + 1;
        }
    }

    cout << answer;
    

    return 0;
}