백준 2110(공유기 설치) c++

문제

2110번: 공유기 설치

n개의 집 위치의 x좌표와 c개의 공유기가 주어지면 거리를 최대로 늘리면서 c개의 공유기를 집에 적당히 설치했을 때

최대 거리를 구하는 문제입니다.

https://st-lab.tistory.com/277 여기서 문제를 자세히 살펴보시면 됩니다.

간단한 이분탐색 문제이지만, 이분탐색에 구현에 있어서 힘들었던 문제입니다.

int l = 1;
int r = *max_element(v.begin(), v.end());

int ans = 0;
while (l <= r)
{
   int mid = (l + r) / 2;
   if (chk(mid) >= c)
  {
     ans = max(ans, mid);
     l = mid + 1;
  }
   else
     r = mid - 1;
}

 cout << ans;

int chk(int distance)
{
	//첫번쨰 집은 무조건 공유기를 설치하므로
    int tmp = 1;  //공유기 1개 설치
    int load = v[0]; //공유기 설치했던 위치
    for (int i = 1; i < v.size(); i++)
    {
        if (v[i] - load >= distance) 
        {
            load = v[i]; //공유기 설치 위치 갱신
            tmp++; //공유기 설치
        }
    }
    return tmp;
}

먼저 이분탐색 부분인 chk함수의 return 타입을 bool로 할지 int로 할지 헷갈렸습니다.

예전처럼 parametric search를 하면 bool형식으로 하면되지만 해당 문제는 공유기를 무제한으로 쓸 수 있습니다.

하지만 공유기를 무한대로 쓰면 그 만큼 집과 집 사이의 거리가 좁아집니다. 따라서 공유기를 c만큼 쓰면서 

최대거리를 구해야 합니다. 

이분탐색은 구현하는 사람마다 차이가 있으므로 저 만의 이분탐색 코드를 만드는 것이 좋을 것 같습니다.

(lower bound, upper bound 포함)

---

전체 코드입니다.

#include <iostream>
#include <string>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
#define INF 2000000000
using namespace std;
using ll = long long;
vector<int> v;
int n, c;
int chk(int distance);
int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n >> c;
    for (int i = 0; i < n; i++)
    {
        int a;
        cin >> a;
        v.push_back(a);
    }
    sort(v.begin(), v.end());

    int l = 1;
    int r = *max_element(v.begin(), v.end());

    int ans = 0;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (chk(mid) >= c)
        {
            ans = max(ans, mid);
            l = mid + 1;
        }
        else
            r = mid - 1;
    }

    cout << ans;

    return 0;
}
int chk(int distance)
{
    int tmp = 1;
    int load = v[0];
    for (int i = 1; i < v.size(); i++)
    {
        if (v[i] - load >= distance)
        {
            load = v[i];
            tmp++;
        }
    }
    return tmp;
}