2110번

2110번 - 공유기 설치

##############다시 풀기##################

이 문제는 종만북에 있는 카메라 설치 문제와 똑같다.

문제를 풀려고 고민하다가 안 풀려서 okay() 함수 부분을 어떻게 구상해야 할지 몰라서 참고해서 풀었다.

최적화 문제를

결정문제 + 최적화문제를 합쳐서 푸는 방식이었다.

공유기 설치하는 방법은 그냥 맨 처음 집부터 설치하는 탐욕적 알고리즘을 사용한다.

(그리디 알고리즘을 공부할 필요가 있다. 설명을 듣고나면 충분히 이해가지만, 어떤 논리적 판단 없이 이런식으로 생각하기는 

어려울 것 같기 때문에)

okay() 함수에서는 특정 거리에서 공유기의 숫자를 K 보다 많이 설치할 수 있는지 판단하는 결정 문제를 푸는 함수이고,

이에 따라 이분탐색을 통해서 최적값을 찾아내는 최적화 문제 를 푸는 방식이다.

종만북 풀때 다시 카메라 문제로 풀어봐야 겠다.

<정답 코드>

#include<iostream>
#include<algorithm>
using namespace std;
int X[100001];
int N, C;
 
bool okay(int c, int mid)
{
    int limit = 0;
    int installed = 0;
    for (int i = 0; i < N; i++)
    {
        if (limit <= X[i])
        {
            installed += 1;
            limit = X[i] + mid;
        }
    }
 
    return installed >= C;
}
int main()
{
    cin >> N >> C;
    for (int i = 0; i < N; i++)
    {
        cin >> X[i];
    }
 
    sort(X, X + N);
 
    int lo = 0;
    int hi = 1000000000;
    int mid;
 
    for (int it = 0; it < 100; it++)
    {
        mid = (lo + hi) / 2;
        if (okay(C,mid))
        {
            lo = mid + 1;
        }
        else
        {
            hi = mid - 1;
        }
    }
 
    cout << mid << endl;
 
    return 0;
}