공유기 설치 - 2110

//2110 - 공유기 설치
 
#include <iostream>
#include <algorithm>
using namespace std;
 
int N, M;
int arr[200000];
 
void init()
{
    cin >> N >> M;
    for (int i = 0; i < N; ++i)
        cin >> arr[i];
    sort(arr, arr + N);
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    init();
    int left = 1;
    int right = arr[N - 1] - arr[0];
    int cnt;
    int ans = -1;
    while (left <= right)
    {
        int mid = (right + left) / 2;
        cnt = 1;
 
        int bidx = 0;
        for (int i = 1; i < N; ++i)
            if (arr[i] - arr[bidx] >= mid)
            {
                bidx = i;
                ++cnt;
            }
 
        if(cnt >= M)
        {
            ans = mid;
            left = mid + 1;
        }
        else
            right = mid - 1;
    }
    cout << ans;
}

 

 

 

 

 

 

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

2110번: 공유기 설치

 

 

 

 

 

 

 

공유기 설치

이분 탐색을 이용했습니다.

두 공유기 거리 사이에 가질수 있는 최소, 최대 값을 구한다음

그 중간값을 후보로 하여 후보값이 정답 조건을 만족하는지 확인하고,

만족하지 않으면 만족하는 값으로 조정,

만족한다면, 더 최적의 조건을 갖는 값으로 조정해서 최적의 값을 찾아내었습니다.