[Algorithm] Baekjoon 2110번 : 공유기 설치

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

2110번: 공유기 설치

 
vector<long long> positions;
int n, c;
 
bool check(int mid)
{
    int count = c - 1;
    int prev = positions[0];
 
    for (int i = 1; i < positions.size(); ++i)
    {
        if (positions[i] - prev >= mid)
        {
            --count;
            prev = positions[i];
        }
        
        if (count == 0) return true;
    }
 
    return false;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> c;
 
    for (int i = 0; i < n; ++i)
    {
        int input;
        cin >> input;
        positions.push_back(input);
    }
 
    sort(positions.begin(), positions.end());
 
    int left = 1;
    int right = positions[n-1] - positions[0];
    int answer = 0;
 
    while (left <= right)
    {
        int mid = (left + right) / 2;
 
        if (check(mid))
        {
            left = mid + 1;
            answer = mid;
        }
        else
        {
            right = mid - 1;
        }
    }
 
    cout << answer;
}
 

어렵지 않은 이분탐색 문제.

최소거리값을 이분탐색으로 결정해 놓고, 그 최소거리를 만족시키면서 주어진 공유기개수를 전부 소모할 수 있는지를 검사하면 된다.

거리값은 최대 10억이지만 이분탐색으로 진행 시 log 1000000000 이라해봤자 30번 될까말까다.

거기에 매번 집개수만큼 하니 log 1000000000 * 200,000이 시간복잡도가 되시겠다.