문제

공유기 설치

풀이

두 집사이에 공유기를 정해진 갯수대로 설치했을때 공유기 사이의 거리를 최대로 할 수 있는 길이를 구하는 것이다. 여기서 공유기가 가지는 coverage는 따로 없고 c의 값만큼만 설치 하면 된다.

항상 이것때문에 어렵다고 느껴지는데 search 하고자 하는 것은
공유기 사이의 최대 거리를 구하는 것이다.
그렇다면 최소의 거리는 1이 된다. 최대의 거리는 정렬했을때
가장 멀리 있는 위치에 있는 공유기에서 가장 가까이 있는 길이를 뺀 값만큼 떨어져 있을것이다.

int answer = 0;

int left = 1; // 최소로 가질 수 있는 길이 (가장 많이 설치하면 모든 곳에 다 설치한다)
int right = a[n - 1] - a[0]; // 가장 먼 길이 (가장 적게 설치하면 딱 한개 만 설치한다)

while (left <= right) { 
	int mid = (left + right) / 2;
    
    int count = 1;
    int prev = a[0];
    for (int i = 1; i < n; i++) {
        // 이전에 설치한 곳과 현재 위치가 비교 길이이거나 클때 설치 하도록 한다
    	if (a[i] - prev >= mid) {
        	count++;
            prev = a[i];
        }
    }
    
    // 설치 개수가 공유기 설치 개수보다 많을때는 범위를 늘려준다
    if (count >= c) {
    	answer = Math.max(answer, mid);
    	left = mid + 1;
    } else {
    	right = mid - 1;
    }
}

전체 코드

전체 코드