[백준_2110번] 공유기 설치

https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

[문제]

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

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

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

 

[입력 조건]

 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

 

[코드]

import java.util.*;

public class BaekJoon_2110 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int c=sc.nextInt();
		int[] house=new int[n];
		
		for(int i=0;i<n;i++)
			house[i]=sc.nextInt();
		
		Arrays.sort(house);
		
		/*
		 * 공유기를 설치할 수 있는 범위는 최소 1부터
		 * 가장 멀리있는 집과 처음의 집 사이의 거리만큼 일 것이다. 
		 * 해당 값들로 start, end를 초기화 해준다.
		 */
		int start=1;
		int end=house[n-1]-house[0]; // 최대길이
		int result=0;
		
		/*
		 * 최소 거리 ~ 최대 거리 범위 내에서 이진 탐색을 사용한다.
		 * 공유기를 설치할 수 있는 지점은 마지막으로 설치한 곳 + 탐색 거리(mid)가 된다.
		 */
		while(start<=end) {
			int mid=(start+end)/2;
			int prevhouse=house[0]; // 첫 번째 집에 설치
			int count=1;
			
			for(int i=0;i<n;i++) {
				int dis=house[i]-prevhouse; 
				/*
				 * 공유기를 설치한 두 지점간의 거리가 탐색중인 mid 보다 크다면
				 * 해당 공유기를 설치할 수 있기 때문에 설치 공유기의 개수를 늘려주고
				 * 마지막으로 공유기를 설치한 집의 위치를 갱신한다.
				 */
				if(dis>=mid) {
					count++;
					prevhouse=house[i];
				}
			}
			
			/*
			 * 설치된 공유기의 개수가 설치하고자 하는 대수보다 작다면
			 * 공유기간의 거리를 줄여서 다시 탐색한다.
			 * 
			 * 설치된 공유기의 개수가 설치하고자 하는 대수보다 많다면
			 * 해당 값을 저장해두고 공유기간의 거리를 늘려 다시 탐색한다.
			 * -> 다음 탐색에서 start<=end 조건을 불만족 한다면 이전에 result에 저장해 둔 값을 출력
			 */
			if(count<c)
				end=mid-1;
			else {
				start=mid+1;
				result=mid;
			}
		}
		System.out.println(result);
	}
}

 

[고찰]

 이번 문제 또한 앞선 두 문제와 결이 비슷했지만 쫌 더 생각해야 하는 문제였다.

이분 탐색을 통해 범위를 조절하면서 고려해야 하는 변수는 공유기 간의 거리이다. 탐색 범위는 최소 거리인 1 부터 최대 거리가 될 수 있는 마지막 집에서 부터 첫 번째 집 까지의 거리이다. 탐색 거리보다 집 사이간의 거리가 작다면 공유기를 설치하고 아니면 다음 집으로 넘어간다. 모든 집을 검사했다면 공유기의 개수에 따라 범위를 조절해야 할 것이다. 설치한 공유기의 개수에 따라 start나 end 값을 변경하여 재 탐색하는 방법으로 문제를 해결할 수 있었다.