2110

공유기 설치 : https://www.acmicpc.net/problem/2110

 

일전에 풀었던 마구간 문제와 같다.

입력받은 x좌표를 오름차순 정렬하고, 선택된 구간 mid를 check함수에서 배치하면서 최적의 d값을 찾아주면 된다.

입력의 첫번째 좌표는 항상 포함시키는 것이 풀이에 있어 팁인것 같다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.*;

public class Main {

	static int N, C;
	static boolean DBG = false;
	static int[] arr;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());

		//st = new StringTokenizer(br.readLine());
		arr = new int[N];
		for (int i = 0; i < N; i++)
			arr[i] = Integer.parseInt(br.readLine());

		int lt = 1;
		int rt = Arrays.stream(arr).max().getAsInt();
		int dMax = 0;
		
		//x배열을 오름차순 정렬
		Arrays.sort(arr);
		
		while (lt <= rt) {
			int mid = (rt + lt) / 2; // distance
			if (C <= check(arr, mid)) {
				dMax = Math.max(dMax, mid);
				lt = mid + 1;
			} else {
				rt = mid - 1;
			}
		}

		System.out.println(dMax);
	}

	static long check(int[] list, long d) {
		long cnt = 1;//설치한 공유기의 수로 1은 항상 포함.
		long now = list[0];
		for ( int i = 0 ; i < list.length ; i++) {
			if( list[i] - now >= d ) {
				cnt++;
				now=list[i];
			}				
		}

		if (DBG)
			System.out.printf("d : %d cnt : %d", d, cnt);
		return cnt;
	}

}