Binary Search

문제설명

문제

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

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

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

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 x_i (1 ≤ x_i ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

접근

이 문제는 이분탐색(Binary Search)을 활용한 문제이다. 이 문제는 가장 인접한 두 공유기 사이의 거리를 최대로 하길 원하기 때문에 가장 인접한 공유기 사이 거리를 기준으로 이분탐색을 수행하면 된다.

입력받은 집의 위치를 정렬한 뒤, 공유기 사이 거리 최소값(mid)를 기준으로 공유기를 설치해 나간다.(공유기 사이 거리가 mid보다 크거나 같으면 설치하고, 작으면 설치하지 않는다.)

공유기 수가 부족하면 간격을 줄이고, 공유기 수를 줄여야 하면 사이 간격을 늘리는 과정을 반복하며 원하는 간격을 찾아낸다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
	vector <long long> v;
	int n, c;
	long long tmp;
	cin >> n >> c;
	for(int i=0; i<n; i++){
		cin >> tmp;
		v.push_back(tmp);
	}
	
	sort(v.begin(), v.end());
	
	long long max = v[n-1] - v[0];
	long long min = 0, ans=0;
	
	while(min <= max){
		long long mid = (max+min)/2;
		long long cnt=1;
		long long installed = v[0];
		
		for(int i=1; i<n; i++){
			if(v[i] - installed >= mid){
				cnt++;
				installed = v[i];
			}
		}
		
		if(cnt >= c){
			min = mid + 1;
			if(ans < mid)
				ans = mid;
		}
		else
			max = mid - 1;
	}
	cout << ans << '\n';
}

참고

BOJ #2110

이 글이 도움이 되셨다면 추천 클릭을 부탁드립니다 :)