BOJ 2110, 공유기 설치
ProblemSolving ·이 문제는 이분탐색 문제입니다.
풀이
처음에 이 문제를 어떻게 이분탐색을 해야하나 고민을 하다가 질문게시판을 보게 되었는데
정답이 되는 값의 범위를 두고 이분 탐색을 하면 된다 라는 말을 보았습니다. 그 말에 아이디어를 얻어 이분탐색을 돌렸습니다.
mid 값(제일 가까운 공유기 사이의 간격) 이상의 갯수를 세주고 그 값이 공유기 수보다 많으면 left 값을 키워주고 적으면 right 값을 키우는 방식으로 답을 구해냈습니다. 많이들 푸신 문제지만 제 생각에 아이디어가 쉽지 않아서 포스팅했습니다.
#include<algorithm>
#include<iostream>
#include<stdio.h>
#include<cmath>
using namespace std;
int n,k,arr[200001];
int main()
{
scanf("%d %d", &n, &k);
for (int i = 0; i < n; i++)
scanf("%d", &arr[i]);
sort(arr, arr + n);
int left = 0, right = 1e9;
while (left <= right)
{
int mid = (left + right) / 2;
int last = 0, t = 1;
for (int i = 1; i < n; i++)
if (arr[i] - arr[last] >= mid)
last = i, t++;
if (k > t)
right = mid - 1;
else
left = mid + 1;
}
printf("%d", right);
return 0;
}