[백준 알고리즘] 2110번: 공유기 설치
March 11, 2021
https://www.acmicpc.net/problem/2110
문제
문제
도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, …, xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.
도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.
C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.
입력
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.
출력
첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.
풀이
이분탐색으로 풀 수 있는 문제인데, 어떻게 풀 것인지 정의하는 것이 어려웠다. 우리가 이분탐색으로 찾을 값은 인접한 두 공유기 사이의 최대 거리이다. 그렇다면 임의의 공유기 사이거리를 설정하고 해당 거리를 최소한으로 공유기를 각 집에 설치해보면, 해당 거리로 설치할 수 있는 공유기의 최대 개수를 알 수 있다.
입력으로 설치할 공유기의 개수가 주어지기 때문에 만약 계산한 공유기의 개수가 설치할 공유기의 개수보다 많다면, 간격을 더 늘려야 된다는 것을 의미하고, 계산한 공유기의 개수가 설치할 공유기의 개수보다 적다면 간격을 줄여서 공유기를 더 늘려주어야 한다. 나는 공유기 설치를 위해서 lowerbound 를 이용했다. lowerbound를 사용하면 인자로 전달한 값 보다 큰 최소값을 set에서 얻을 수 있기 때문에 특정한 사이거리 이상의 집 중 가장 가까운 곳에 공유기를 설치해볼 수 있다.
코드
' '
#include <cstdio>
#include <set>
using namespace std;
set<int> houses;
int N, C;
int installRouter (int interval){
int count = 1;
int point = *(houses.begin()) + interval;
while(true){
auto iter = houses.lower_bound(point);
if (iter != houses.end()) {
count++;
}
else if (iter == houses.end()) break;
point = *iter + interval;
}
return count;
}
int binarySearch(){
int head = 1;
int tail = *(houses.rbegin());
int answer = 0;
while(head <= tail){
int mid = (tail + head) / 2;
int result = installRouter(mid);
if (result >= C) {
head = mid + 1;
answer = mid;
}
else tail = mid - 1;
}
return answer;
}
int main (){
scanf("%d %d", &N, &C);
for (int i = 0 ; i < N ; i++){
int house;
scanf("%d", &house);
houses.insert(house);
}
printf("%d", binarySearch());
}
