[BaekJoon] 2110 공유기 설치

1.  문제 링크

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

2.  문제

요약

• N개의 집이 수직선 위에 있는데 이 집들에 공유기 C개를 설치하는데 한 집에는 공유기 한 개만 설치할 수 있습니다.
• 최대한 많은 곳에서 와이파이를 사용하기 위해 가장 인접한 두 공유기 사이 거리를 가능한 크게 설치하려고 할 때, C개의 공유기를 N개의 집에 적당히 설치해서 가장 인접한 두 공유기 사이 거리의 최댓값을 구하는 문제입니다.
• 입력: 첫 번째 줄에 2보다 크거나 같고 200,000보다 작거나 같은 집의 개수 N과 2보다 크거나 같고 N보다 작거나 같은 공유기 개수 C가 주어지고 두 번째 줄부터 N개의 줄에는 0보다 크거나 같고 1,000,000,000보다 작거나 같은 집의 좌표 xi들이 주어집니다.
• 출력: 첫 번째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
	public int findGateWayNum(long length, int[] house_location) {
		int count = 1;
		int prev_loc = house_location[0];
		for(int i = 1; i < house_location.length; i++) {
			if(house_location[i] - prev_loc >= length) {
				count++;
				prev_loc = house_location[i];
			}
		}
		return count;
	}
	
	public long getMaxGatewayNum(int gateway_num, int[] house_location) {
		Arrays.sort(house_location);
		long start = 1;
		long end = (long)house_location[house_location.length - 1] - house_location[0] + 1;
		while(start < end) {
			long mid = (start + end) / 2;
			if(findGateWayNum(mid, house_location) < gateway_num) {
				end = mid;
			} else {
				start = mid + 1;
			}
		}
		return start - 1;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] input = br.readLine().split(" ");
		int house_num = Integer.parseInt(input[0]);
		int gateway_num = Integer.parseInt(input[1]);
		int[] house_location = new int[house_num];
		for(int i = 0; i < house_location.length; i++) {
			house_location[i] = Integer.parseInt(br.readLine());
		}
		br.close();
		Main m = new Main();
		bw.write(m.getMaxGatewayNum(gateway_num, house_location) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 이 문제는 이진 탐색을 이용하여 해결할 수 있는 문제입니다.
• 공유기 사이의 최소 거리에 따라서 설치할 수 있는 공유기의 개수가 달라지기 때문에 설치해야 할 공유기의 개수가 문제에 주어져있으니 해당 개수만큼 공유기를 설치할 때의 공유기 사이의 최소 거리를 최대로 하는 거리를 찾아야 합니다.
• 그렇기 때문에 거리를 변경해가면서 해당 거리에서 공유기를 몇 개 설치할 수 있는지 확인하며 거리의 범위를 좁힙니다.
• 거리를 늘리면 설치할 수 있는 공유기 개수가 줄어들고 거리를 줄이면 설치할 수 있는 공유기 개수가 늘어나기 때문에 이를 이용하여 범위를 줄입니다.

1. 주어진 집의 좌표들을 오름차순으로 정렬합니다.
2. 두 공유기 사이 거리로 최소로 가질 수 있는 거리 1을 start라는 변수에, 최대로 가질 수 있는 거리를 end라는 변수에 설정합니다.
3. start 변수의 값이 end 변수의 값보다 작을 동안 반복문을 돌며 인접한 두 공유기 사이의 최대 거리를 구합니다.
   1. 이진 탐색을 진행하기 위해 start와 end의 중간값을 mid라는 변수에 설정하고 두 공유기 사이 최소 거리가 mid일 때의 설치할 수 있는 공유기 개수를 구합니다.
      1) 첫 집에 공유기가 설치되어 있다 가정하고 설치되어 있는 공유기 개수를 나타내는 변수인 count의 값을 1로 설정하고 직전에 공유기를 설치한 집을 나타내는 변수인 prev_loc의 값을 첫 번째 집의 좌표로 설정합니다.
      2) 전체 집들을 돌면서 직전에 공유기를 설치한 집과 현재 집 사이의 거리가 두 공유기 사이 최소 거리보다 크거나 같다면 공유기를 설치할 수 있기 때문에 count 값을 1 증가시키고 직전에 공유기를 설치한 집을 나타내는 prev_count 변수의 값을 현재 집 좌표로 변경합니다.
      3) 모든 집을 다 돌았을 때의 count 변수의 값이 설치할 수 있는 공유기의 개수입니다.
   2. 설치할 수 있는 공유기 개수가 주어진 공유기 개수보다 작다면 공유기를 더 설치해야 하므로 두 공유기 사이의 최소 거리를 줄여야 하기 때문에 end 변수의 값을 mid 변수의 값으로 변경합니다.
   3. 만약 설치할 수 있는 공유기 개수가 주어진 공유기 개수보다 크거나 같다면 공유기를 덜 설치해야 하므로 두 공유기 사이의 최소 거리를 늘려야 하기 때문에 start 변수의 값을 (mid 변수의 값 + 1)로 변경합니다.
4. 3번의 반복문이 끝났을 때의 start 변수의 값에 1을 빼준 값이 가장 인접한 두 공유기 사이의 최대 거리가 되어 이를 출력합니다.