백준 2110 - 공유기 설치

Java

2110 번 - 공유기 설치

문제

접근 방법

이분 탐색의 응용 문제였다.
이분 탐색의 주체를 두 집 간격의 거리라고 생각한다.

가장 큰 집 사이의 간격은 첫번째 집(arr[0])과 마지막 집(arr[n - 1])의 사이 간격이며,
이 간격 부터 시작하여 절반 씩 나누며 최적의 집 사이의 간격을 구한다.

알고리즘은 다음과 같이 동작한다.

1. 최소 집 사이 거리 = 1, 최대 집 사이 거리 = 마지막 집 - 첫 집 를 설정한다.
2. mid = (최소 집 사이 거리 + 최대 집 사이 거리) / 2 를 기준으로 몇개의 공유기를 설치 할 수 있는지 확인한다.
   1. 현재집(curN) + mid 의 위치보다 크거나 같은 곳에 있는 집에 공유기를 설치한다(nextN)
   2. 반복하며 주어진 집 범위 내에서 M 개의 공유기를 모두 설치 할 수 있는지 확인
3. 공유기를 M 개 보다 적게 설치했다면, mid(현재 간격)이 너무 커서, 공유기를 다 설치 못한 것이므로, 최대 공유기 사이 거리 값 조정
4. M 개 설치 했다면 현재의 mid 값 저장
5. M 개 이상 설치했다면 집 사이 간격 거리를 늘린다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, result, m, start, end;
	static int[] house;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());

    	house = new int[n];
    	for(int i = 0; i < n; i++) {
    		house[i] = stoi(br.readLine());
    	}

    	Arrays.sort(house);

    	binarySearch(1, house[n - 1] - house[0]);


    	System.out.println(result);
    	br.close();
	}

	static void binarySearch(int low, int high) {

		int mid = (high + low) / 2; // 최대 거리와 최소 거리의 중간

		int router = 1; // 첫번째 공유기 설치
		int curN = 0, nextN = 1;		// 집의 인덱스

		if(low <= high) {

			while(nextN < n && router < m) {
				// 현재 거리만큼 더했을 때 다음 집에 공유기를 설치 할 수 있는지
				if(house[nextN] >= house[curN] + mid) {
					router++;
					curN = nextN;
					nextN++;
				}
				else {	// 다음 집을 선택하여, 거리만큼 더했을 때 보다 더 간격이 넓어지도록 한다.
					nextN++;
				}
			}

			if(router == m) {		// 성공 조건, 집 시작부터 끝 사이의 거리 내에 공유기를 설치하였다.
				result = mid;
				binarySearch(mid + 1, high);	// 간격 늘리기, 최선의 값을 구한다
			}
			else if(router < m) {	// 라우터를 다 설치 못했을 시, 간격을 줄인다.
				binarySearch(low, mid - 1);
			}
			else {		// 간격 늘리기
				binarySearch(mid + 1, high);
			}

		}


	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}