✨ 문제

백준 2110 공유기 설치

🎈 접근 방식

1. 공유기 사이의 거리를 정하고 그에 따라 C개만큼 설치가 가능한지 확인해야 한다.
2. 이에, 이진 탐색을 활용하도록 생각했다.
3. 제일 최솟값은 1이 될 것이다. 같은 좌표에 공유기를 설치하는 일은 없기 때문이다. 최댓값은 제일 끝에 있는 집의 좌표에서 첫 번째 집의 좌표를 빼주면 될 것이다.
4. 이로써, left와 right 초기 값이 정해졌으니 이진 탐색을 실시하면 된다.

처음에는 조합을 생각해보았지만, 시간초과가 발생할 것으로 생각이 되었기 때문에 이진탐색으로 공유기 사이의 거리의 최댓값을 계속해서 찾아나가기로 했다.

😫 실수한 점이나 놓친 점

아무래도 처음에 조합으로 접근하려고 했던게 미스였던 부분이라고 생각된다. 문제를 보고 시간복잡도도 조금 고려를 해야 할 때라고 생각은 되는데 아직 익숙치 않은 부분인 것 같다.
조금 더 시간적으로나 효율적인 방법이 없는지 좀 더 고민을 해야겠다!

💻 풀이 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
		int[] houses = new int[N];

		for (int i = 0; i < N; i++) {
			houses[i] = Integer.parseInt(br.readLine());
		}

		// 이진 탐색을 위한 정렬
		Arrays.sort(houses);

		// 공유기가 같은 좌표에 있지는 않을거니깐 최소 거리차이는 무조건 1
		int left = 1;
		// 초기에 고려해볼 수 있는 거리의 최댓값은 맨 뒤에에서 맨 앞에 거리 뺀 것
		int right = houses[N - 1] - houses[0];
		int maxDistance = 0;

		while (left <= right) {
			// 중앙값 (즉, 공유기 사이의 거리)
			int mid = (left + right) / 2;

			// 첫번째 집을 먼저 기준으로 잡고
			int standHouse = houses[0];
			// mid랑 비교해보면서 공유기가 설치 가능한 집의 개수
			int countHouse = 1;
			
			for (int i = 1; i < N; i++) {
				if (houses[i] - standHouse >= mid) {
					countHouse++;
					standHouse = houses[i];
				}
			}
			
			// C개 이상만큼 공유기 설치가 가능해진다면 maxDistance를 갱신해주고
			if (countHouse >= C) {
				maxDistance = mid;
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		}

		System.out.println(maxDistance);
	}
}