[PS] BOJ2110 공유기 설치 ( BinarySearch ) with JAVA

 

2110번: 공유기 설치

 

 

◎ 문제풀이 

 

개인적으로 이분탐색 발상이 어려운 문제였다.

 

 

 

 

'가장 인접한 두 공유기 사이의 최대거리를 구하라.' 의 의미를 제대로 파악해야 한다. 

 

처음에는 공유기 개수가 3대라면, 1번, 8번, 9번에 공유기를 설치하면 1번과 8번 사이가 7이 되니 최대거리는 7이 아닌가 싶었다. 근데 이런 것을 물어보는 문제가 아니었다. 

 

인접한 두 공유기 사이의 거리의 범위는 1 [두집 사이 최소거리] 과 8[1번 집 - 9번 집] 사이이다.

 

 

만약 인접한 두 공유기 사이의 거리가 1이라면 위 그림과 같다. 공유기는 총 5대 설치할 수 있다.

 

 

 

 

만약 인접한 두 공유기 사이의 거리가 8이라면 위 그림과 같다. 공유기는 총 2대 설치할 수 있다.

 

이렇듯 ,공유기 사이의 거리에 따라 설치될 수 있는 공유기의 개수가 다르다. 만약 공유기를 3대를 설치한다고 했을 때, 3대 설치가 가능한 최대거리를 구하는 것이 이 문제의 목적이다. 그러므로 1과 8 사이에서 이분탐색을 해야하는 것이다. 

 

이 문제가 어려운 또 하나의 이유가 있다.

 

바로 범위설정이다. 이 문제는 최대거리를 구해야 한다. 다시 말하여, 3대를 설치할 수 있는 거리가 한 개가 아니라는 말이다. 이분탐색은 start와 end 사이의 mid 값을 구한다.  mid의 거리로 공유기를 3대 설치가 가능하다고 해도, mid가 최대거리라는 보장이 없다. 그러므로 계속 탐색을 이어가야 한다. 

 

 

[PS] BOJ1654 랜선 자르기 ( BinarySearch ) with JAVA

( 이 문제와 동일한 문제에는 랜선 자르기 문제가 있다. )

 

 

 

start가 있고 end가 있고 중간에 mid가 있다.

 

mid로 공유기 3대 설치가 가능하다고 해도, 최대거리라는 보장이 없다.  그래도 현재 mid가 공유기 3대 설치가 가능한 mid 중 최대거리라는 점은 확실하다. 그러므로 더 큰 최대거리를 구하기 위해 탐색을 이어가야 한다.

 

start를 mid+1로 하여 우측범위를 탐색한다.

 

 

 

우측범위의 mid를 구했는데, 또 다시 3이 나왔다면, 공유기 3대 설치가 가능한 mid의 최대거리가 갱신된 것이다. 그럼 다시 start를 mid+1로 하여 우측범위를 탐색한다.  만약 3보다 큰 값이 나온다면 end를 mid-1로 하여 좌측범위를 탐색한다. 그럼 언제까지 탐색해야 할까? 바로 start가 end보다 커질 때까지 이다. 이분할 수 없을때까지 탐색하여 최대거리를 구해야 한다.  그렇다면 마지막 탐색에서 start, mid, end는 모두 동일한 값이 된다. 탐색할 때마다 +1 혹은 -1 씩 증감이 되기에 start와 end는 어느순간 같아진다.

 

마지막 탐색에서 경우는 두 가지가 된다. 

 

1) 마지막 탐색에서 최대거리가 갱신된 경우

 

 

 

 

start, mid, end가 5라고 가정해보자.  인접한 공유기 사이 거리가 5일 때, 공유기를 3대 설치가 가능하다면 최대거리는 갱신된다. 최대거리가 갱신되었으므로 mid + 1하여 다음 탐색의 start로 지정한다. 그랬더니 start가 end보다 커졌다. 더이상 이분할 수 없으니 이분탐색을 종료한다. 

 

최종적으로 공유기 3대를 설치할 수 있는 인접한 공유기 사이 거리의 최댓값은 5가 된다. 

 

그러므로 다음탐색에서 mid와 값이 동일한 end가 최대거리가 된다. 

 

2) 마지막 탐색에서 최대거리가 갱신되지 않은 경우 

 

 

 

 

start, end, mid가 6이라고 가정해보자. 인전한 공유기 사이의 거리가 6일 때, 공유기 3대 설치가 가능하지 않다면 최대거리는 갱신되지 않는다. 최대거리는 mid에 -1을 한 5가 된다.  우측에 있다는 말은 최대거리로 갱신된 mid에 +1한 값을 start로 하여 탐색했다는 의미이다. 다시 말하여, 마지막 탐색은 mid가 5일 때 최대거리가 갱신되어 mid+1한 6을 start로 한 탐색이라는 의미이다. start는 6이고, end도 6이니, mid도 6이 된다. mid가 6일 때 최대거리가 갱신되지 않는다면 mid-1이 최대거리가 된다. 

 

그러므로 다음탐색에서 mid-1과 값이 동일한 end가 최대거리가 된다.

 

1번 경우와 2번 경우 모두 end가 최대거리가 되므로, 이분탐색이 종료되었을 때 최대거리는 end에 저장되어 있다.

 

그럼 코드로 이를 확인해보자. 

 

 

◎ 코드

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

//BOJ2110 공유기 설치
public class Main {

    public static void main(String[] args) throws IOException {
        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); // 오름차순 정렬 

        int start = 1; // 공유기 사이 거리 최솟값
        int end = houses[n-1] - houses[0]; // 공유기 사이 거리 최댓값
        while(start <= end){ // start가 end보다 커지면 이분탐색 종료 
            int mid = (start+end)/2;
            int count = getWifiCount(houses,mid); // 설치 가능한 공유기 개수 구하기

            if(count >= c) start = mid+1; // mid가 갱신된 경우
            else end = mid-1; // mid가 갱신되지 않은 경우
        }

        System.out.println(end); // 최대거리가 저장된 end를 출력
    }

    public static int getWifiCount(int[] houses, int length){
        int count = 0;
        int value = 0;
        for (int house : houses) {
            if( value == 0 || value <= house){
                value = house + length;
                count++;
            }
        }
        return count;
    }
}