백준(BOJ) 2110번 공유기 설치

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

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

나의 풀이:

집들의 간격을 오름차순으로 정렬한다. 그 후 최소 간격수와 최대 간격수를 정한다. 최소 간격수와 최대 간격수 사이에 간격을

 이분 탐색으로 접근한다. 조건이 만족하면 간격을 저장한다. 조건을 만족하는 더 큰 간격이 있는지 확인하기 위해 간격을 높

인다.  조건을 만족하지 않는다면 간격을 낮춘다.

solve 함수 예시)

코드 ( C ++ )

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

int N, C;

vector<int> v;

bool solve(int gap)

{

int cnt = 1;

int first = v[0];

for (int i = 1; i < N; ++i)

{

// 간격이 gap보다 크다면 조건만족

// cnt 증가후 first 를 갱신해준다.

if (v[i] - first  >= gap) {

cnt++;

first = v[i];

}

}

if (cnt >= C) return true;

else return false;

}

int main()

{

ios_base::sync_with_stdio(false);

cin.tie(0);

cin >> N >> C;

for (int i = 0; i < N; ++i) {

int num;

cin >> num;

v.push_back(num);

}

sort(v.begin(), v.end());

// 최소 간격수는 1이여야한다.

int small = 1;

// 최대 간격수는 마지막집 - 처음 집이다.

int big = v[v.size() - 1]- v[0];

int ret = 0;

while (small <= big) {

int mid = (small + big) / 2;

if (solve(mid)) {

// 조건을 만족하는 mid 중 가장 큰 mid를 ret에  저장한다.

ret = max(ret, mid);

//간격을 높여준다.

small = mid + 1;

}

else {

// 간격을 낮춘다.

big = mid - 1;

}

}

cout << ret << "\n";

return 0;

}