[BOJ] 2110 공유기 설치 - Java

[문제]

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

[문제 풀이]

우선 집의 좌표를 배열에 다 넣어주고 오름차순으로 정렬한다.

이분 탐색을 이용해서 두 공유기 사이의 최대 거리를 찾아줄 것이다.

가능한 범위는 1 부터  마지막 집과 첫 집 사이의 거리이므로

s = 1, e = arr[N-1] - arr[0]으로 초기화 시켜주었다.

그 다음 m = (s+e)/2 가 된다.

공유기 설치한 마지막 집을 left라고 두자.

left와 다음 집 사이의 거리가 m 보다 크면 공유기를 설치할 수 있으므로 cnt를 증가시키고 left = arr[i] 가 된다.

공유기 설치가 끝나면 문제에서 주어진 c개인지 확인해야한다.

공유기를 설치한 cnt 값이 c보다 많거나 작다면 m을 늘려주어야 하므로

ans = m, s = m+1로 만들어준다.

c보다 크면 m을 줄여주어야 한다. 따라서 e = m-1이 된다.

다 돌면 ans를 출력해 주면 된다.

 

 

[코드]

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

public class Main {
	
	static int N, C;
	static int[] arr;
	
	static int stoi(String s) {
		return Integer.parseInt(s);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = stoi(st.nextToken());
		C = stoi(st.nextToken());
		arr = new int[N];
		
		for (int i=0; i<N; i++) {
			arr[i] = stoi(br.readLine());
		}
		Arrays.sort(arr);
		
		int ans = 0;
		
		int s = 1;
		int e = arr[N-1] - arr[0];
		while (s <= e) {
			int m = (s + e) / 2;	// 거리
			int left = arr[0];		// 이전 공유기 설치한 집
			int cnt = 1;			// 공유기 설치한 갯수
			
			for (int i=1; i<N; i++) {
				// 차이가 m 보다 크면 설치 가능
				if (arr[i] - left >= m) {
					cnt++;
					left = arr[i];
				}
			}
			// 공유기 설치 끝
			
			// 설치한 공유기가 C보다 많거나 같으면 줄여야함
			if (C <= cnt) {
				ans = m;
				s = m + 1;
			} else {	// 설치한 공유기가 부족하면 늘려야 함
				e = m - 1;
			}
		}
		System.out.println(ans);
	}
}

[실행 결과]

결과는 위와 같다.