이분탐색 - 백준 2110번 공유기 설치

www.acmicpc.net/problem/2110

2110번: 공유기 설치

IDEA

두 공유기 사이의 최대 거리를 구하는 문제다. 

거리는 1부터 시작해서 최대 정렬했을 떄 기준 arr[n-1] - arr[0] 까지이다. 

거리는 단조증가한다 -> 거리에 대해서 이분탐색을 적용할 수 있다.

 

• 정렬 시 인접한 공유기 사이의 최단 거리 = 1 , 최장 거리 = arr[n-1] 이므로 start = 1 , end = arr[n-1]로 설정한다
• for문을 돌며 거리값(arr[i] - prev)이 mid보다 크다면 공유기를 설치해준다.
  prev는 이전 공유기가 설치되어있는 값을 얘기한다. 
• 공유기 설치 개수 (count )와 내가 설치하고자 하는 개수(c)의 대소관게를 비교한다.
• 만약 count > c 이라면 간격을 넓혀야하므로 start = mid +1 
• 또 count == c 일 때, 최댓값이라고 확신할 수 없으므로 간격을 조금씩 더 넓혀 확인해보아야한다.
  그러므로 answer에 값을 저장해둔 후 start = mid+1 을 진행해 확인해본다. 
• 만약 count < c 라면 간격을 좁혀야하므로 end = mid -1 

* 나는 여기서 start = arr[0] 로 두어 애를 먹었다. 

4 5 6 7 중 3개를 고르라면 답은 1이야한다. start = arr[0] = 4 로 두면 답이 절대 안나온다.

* 또 정확하게 얘기하면 최장 거리는 정렬했을 때 기준 arr[n-1] - arr[0] 이다. 하지만 귀찮아서 arr[n-1] 로 뒀다.

code

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

vector<int >arr;

int main() {
	int n, c;
	
	scanf("%d %d", &n, &c);
	for (int i = 0; i < n; i++) {
		int  num;
		scanf("%d", &num);
		arr.push_back(num);
	}
	sort(arr.begin(), arr.end());

	int answer = 0;
	int start = 1,  end = arr[n-1] - arr[0] ;

	while (start <= end) {

		int mid = (start + end) / 2;
		int prev = arr[0];
		int count = 1; //공유기의 개수 
		
		for (int i =0 ; i < n; i++) {
			if (arr[i] - prev >= mid) {
				count++;
				prev = arr[i];
			}
		}

		if (count < c) end = mid - 1;
		else {
			start = mid + 1;
			answer = mid;
		}
	}
	printf("%d", answer);
}