문제
풀이
거리의 최솟값 1을 left로 거리의 최대값 arr[N-1] - arr[0]을 right로 설정하여 이분탐색을 진행한다. mid = (left+right)/2로 설정하여 그 간격 이상에 위치한 집에 공유기를 설치했을 때 설치하려는 공유기 수 보다 많은 값이 나오면 간격을 늘려서(left = mid + 1로 바꾸어서 간격을 늘린다), 설치하려는 공유기 수보다 작은 값이 나오면 간격을 줄여서 (right = mid - 1로 바꾼다.) left가 right를 초과할 때 까지 진행한다. 원하는 정답은 while문을 빠져나올 때의 최종 mid값이 답이 된다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
int N, C;
scanf("%d %d", &N, &C);
vector<int> arr(N);
for(int i = 0; i<N; i++){
scanf("%d", &arr[i]);
}
sort(arr.begin(), arr.end());
int left = 1;
int right = arr[N-1] - arr[0];
int result = 0;
while(left<=right){
int cnt = 1;
int mid = (left+right)/2;
int tmp = arr[0];
for(int i = 1; i<N; i++){
if(arr[i] - tmp >= mid){
cnt++;
tmp = arr[i];
}
}
if(cnt>=C){//간격을 늘려야 함
result = mid;
left = mid + 1;
}
else//간격을 줄여야 함
right = mid - 1;
}
printf("%d\n", result);
}
