[ Baekjoon ] 2110. 공유기 설치

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

2110번: 공유기 설치

풀이 방법

N개의 집 중 C개의 집에 공유기를 설치하는 모든 경우의 수는 이다. 각 경우의 수에 대하여 최소 인접 거리를 구하는 것은 O(C)의 시간이 걸리기 때문에 전체 시간복잡도는 이다. Brute force 방식으로 모든 경우의 수에 대하여 계산하면 시간 초과가 발생한다. 따라서 이진 탐색을 활용해 인접한 공유기 사이의 최소 거리를 찾아내도록 하자.

 

먼저 주어진 집들의 위치를 오름차순으로 정렬한다.

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

 

이때 공유기를 설치할 수 있는 간격은 1부터 가장 멀리 떨어진 두 집 사이의 거리 중 하나의 값이다. 공유기 사이의 최소 간격을 m으로 설정하여 최대한 많이 공유기를 설치했을 때, 설치한 공유기 개수 cnt에 대해 다음과 같이 유추할 수 있다.

• C보다 cnt가 크면, 설치 간격이 너무 좁다는 뜻이다. 따라서 설치 간격을 좀 더 넓혀본다.
• C보다 cnt가 작으면, 설치 간격이 너무 넓다는 뜻이다. 따라서 설치 간격을 좀 더 줄여본다.

이를 바탕으로 설치 간격을 이진 탐색을 통해 찾아보자. 단, 가장 인접한 공유기 사이의 간격이 최대가 되는 경우를 찾기 위해서 다음과 같이 경우를 나누자.

• C가 cnt보다 크거나 같으면, 현재 간격을 잠시 저장해두고 설치 간격을 좀 더 넓혀본다.
• C보다 cnt가 작으면, 설치 간격이 너무 넓다는 뜻이다. 따라서 설치 간격을 좀 더 줄여본다.

코드로 나타내면 다음과 같다.

int left = 1, right = x[N-1]-x[0];
int ret = -1;
while(left <= right){
	int mid = left + (right - left) / 2;
	int install = 0, cnt = 1;
	for(int i=1; i<N; i++){
		if(mid <= x[i] - x[install]){
			cnt++;
			install = i;
		}
	}
	if(cnt >= C){ // too close
		ret = mid;
		left = mid + 1;
	}
	else{ // too far
		right = mid - 1;
	}
}

 

이렇게 이진 탐색을 통해 구현하면 전체 시간 복잡도는 O(NlogN)이다.

 

전체 코드는 여기서 확인할 수 있다.