문제 이해

숫자 배열이 주어질 것이다. 이 때 배열 값의 위치에 공유기를 설치할 수 있다.
공유기를 설치하는 방법은 아래와 같다.

1. 내가 지정할 수 있는 임의의 수 K가 존재한다.

2. 숫자 배열에서 특정 수 T가 존재한다고 가정하자.
   (1) 만약 T-K < X < T+K인 어떤 X 위치에 공유기가 설치되어 있다면 해당 위치(T)에는 공유기를 설치하지 않아도 된다.
   (2) 설치되어 있지 않다면 무조건 T에는 설치되어야 한다.

즉, 임의로 공유기를 설치했을 때, 모든 배열에 존재하는 숫자에 대하여 (1) 조건을 만족시키면 문제의 조건을 충족시키는 것이다.

이 때 내가 설치하고 싶은 공유기는 C개이며, 가장 가까운 공유기 사이의 거리 값을 최대로 하는 문제이다.(즉, K값을 최대한 크게 하는 것이다)

문제 풀이

먼저 여기에서 중요한 점이 있다.

"꼭 공유기는 C개 설치할 필요가 없다"

문제에서는 C개 설치하라 그랬는데 이게 뭔 소리냐고 물어볼 수도 있다.
정확히 말하자면 C개 이상 설치해서 문제 조건을 충족시킬 수 있다면, 이는 C개 설치한 것과 동일한 효과를 가진다는 것이다.

예를 들어보자.
1 2 3 4 5라는 배열이 존재하고 있다.
C = 2일 때, 우리는 답이 2이라는 것을 쉽게 알 수 있다. (2, 4에 설치)
하지만, 1, 3, 5에 설치해도 답이 2이지만, 설치된 공유기 수는 3개이다.
즉, 내가 설치한 공유기가 C 이상이기만 하다면, 이 공유기를 적절히 조절해서 C개로 만들 수 있다.

그렇다면 C를 어떻게 활용할 수 있을까?
만약 공유기를 T개 설치했다고 가정하자. 그리고 K는 가장 인접한 공유기 사이의 거리이다.

1. T >= C : 정답이 될 가능성이 있는 Case이다.
   하지만 우리는 최댓값을 구하고 싶기 때문에 지금 내가 설정한 값보다 더 큰 K를 설정하여 공유기를 다시 설치해본다.

2. T < C : 정답이 될 수 없는 Case이다.
   K가 너무 크기 때문에 굳이 C개를 설치하지 않아도 조건을 만족시켜버리는 경우이다. 우리는 무조건 C개를 설치하고 싶기 때문에 K를 작게 설정하여 공유기를 다시 설치한다.

• C개 미만일 경우에는 억지로 공유기를 추가로 설정할 경우 인접한 공유기 사이의 거리가 줄어들기 때문에 임의로 지정한 K값이 변동되므로 정답이 될 수 없다.
  (ex) 1 2 3 4 5에서 K = 5로 지정할 경우 1에만 설치해도 조건을 충족시킨다. 하지만 억지로 (1,5)에 설치해버리면, K = 4로 변동된다. 이 경우 알고리즘 자체에 문제가 발생하므로 일어나서는 안되는 상황이다.

따라서 이분탐색을 통해 문제를 해결하였다.

코드

import java.io.*;
import java.util.*;

public class Main {
	static int N;
	static int C;
	static int[] arr;
	
	static void wifi(int right) {
		int mid;
		int left = 1;
		int ans = 0;
		
		while(left <= right) {
			int last = arr[0]; // last : 최근에 설치한 공유기 위치
			int count = 1;
			mid = (left + right)/2; 
            // 내가 임의로 지정한 가장 인접한 두 공유기 사이의 거리

			for(int i = 1;i<N;i++) {
				if(last + mid <= arr[i]) {
                /*
                마지막으로 설치한 공유기 위치  
                    + 가장 인접한 두 공유기 사이의 거리 <= 현재 위치
                    
                문제 이해 중 2.(2) 상황
                
                새롭게 공유기를 설치해야 하므로 last값을 현재 위치로 바꾸고
                공유기 수를 1 증가 시킨다.
                */
					last = arr[i];
					count++;
				}
			}
			
			if(count >=  C) {
                // 문제 풀이 1번 상황
                // 답이 될 가능성이 존재(ans에 mid값 저장)
                // & 큰 값 Search(left값 변환)
				ans = mid;
				left = mid + 1;
			}
			else {
                // 문제 풀이 2번 상황
                // 작은 값 Search(Right값 변환)
				right = mid - 1;
			}
		}
		
		System.out.println(ans);
	}
	
	
	public static void main(String[] args) {
		FastReader sc = new FastReader();

		N = sc.nextInt();
		C = sc.nextInt();
		arr = new int[N];
		
		for(int i =0;i<N;i++) {
			arr[i] = sc.nextInt();
		}
		Arrays.sort(arr); // 아래 참조 확인
		
		wifi(arr[N-1] - arr[0]);
        // 두 공유기 사이의 거리는 숫자 배열의 최댓값과 최솟값의 차이보다 
        // 클 수는 없다.
        // 따라서 초기 right을 arr[N-1](최댓값)-arr[0](최소값)으로 설정해준다
	}
	
	static class FastReader // 입력을 빨리 하기 위한 클래스. 생략
}

결과

• 5, 6번째 틀렸습니다 : 설치한 공유기 수 > C일 때도 정답이 될 수 있다는 점을 간과하여 틀렸다.

• 3, 4번째 틀렸습니다 : 설치한 공유기 수 < C일 때도 정답이 될 수 있게 코드를 짜 틀렸다.

참조

이 문제는 앞서 풀었던 나무 자르기와 동일하게 left와 right가 자연수임을 알 수 있다. 즉, left와 right은 배열값과 관계 없기 때문에 배열의 정렬이 필요 없다고 생각할 수 있다.

하지만, 이 문제에서 숫자는 좌표를 의미한다는 점이 중요하다.

만약 좌표가 정렬되어 있지 않다면, (다음 좌표 - 지금 좌표)가 음수가 될 수도 있다. 만약 음수까지 고려하게 된다면 알고리즘이 더욱 복잡해 질 것이다.
따라서, 좌표값을 정렬시켜 무조건 (다음 좌표 - 지금 좌표)를 양수로 만드는 것이 필요하다.
즉, 이번 Sorting은 이분 정렬을 위한 Sorting이 아닌 알고리즘을 조금 더 쉽게 만들어주는 Sorting이다.

• 이분 탐색에 필요한 Sorting은 left, right, mid를 자연수 배열에서 사용하는 것과 비슷하기 때문에 이미 되어있다고 생각할 수 있다.