백준, 공유기 설치(2110, java)

문제 설명

집 N개가 같은 좌표를 가지는 일이 없게 수직선 위에 서 있다. 이때 도현이는 와이파이를 각 집에 설치해서 최대한 많은 곳에서 인터넷을 사용하려고 한다. 와이파이는 한 집에 하나만 설치할 수 있고 가장 인접한 두 공유기 사이의 거리를 최대로 하려고 한다. 해당 값을 구하는 문제이다.

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

2110번: 공유기 설치

문제 풀이

첫 번째 접근

일단 부르트포스(완전 탐색)으로 풀 수 있지만, 집의 개수가 최대 200,000개이니 굳이 시도하지 않아도 시간 초과가 날 것을 짐작할 수 있다.

 

그렇다면 어떻게 효율적으로 정답을 구할 수 있을까? 바로 이진탐색이다.

이진탐색에서는 어떤 것을 기준으로 탐색하는 것이 중요한데, 거리를 구하는 문제이니까 거리를 기준으로 탐색을 해줬다.

 

문제 풀이 초반에는 맨 끝 두 부분에 와이파이를 설치하고 나머지는 계속 최대를 찾다가 마지막에 최소를 찾으면 된다고 생각했다.

예를 들어서 집이 [1, 2, 4, 6, 7, 9] 좌표에 있고 와이파이를 총 4개 설치한다고 생각해 보자.

 

먼저 집 1과 9에 와이파이를 설치한다.

그러면 와이파이가 총 2개 남았고 이 거리의 중간은 6이다. 1에서 6까지의 거리가 6에서 9까지의 거리보다 크니까 6에 와이파이를 설치한 후 1에서부터 6까지의 거리를 탐색한다. 이때 중간 값은 4이고 와이파이가 1개 남았으므로 1부터 4와 4부터 6중 제일 작은 숫자인 2가 답이되는 것이다.

 

즉, 최대 거리 중 최소를 찾으라고 했으니 1이 남기 전까지는 이분탐색으로 최대 거리를 찾다가 와이파이가 1이 되는 순간 최소 거리를 찾는 아이디어이다.

 

해당 풀이는 예제나 질문에 있던 반례들을 넣었을 때 제대로 된 값이 나와 맞은 줄 알았다.

 

그러나

 

아래의 예시를 한 번 보자.

집의 수 6, 와이파이의 수 4

집의 좌표 [1, 3, 4, 5, 9, 13]

 

1. 와이파이를 양쪽 끝인 1과 13에 설치한다. 이제 와이파이는 총 2개가 남았다.

2. (0+5)/2 = 2로 1부터 4까지와 4부터 13까지의 거리를 비교한다.

3. 4부터 13까지의 거리가 길기에 4에 와이파이를 하나 두고 4부터 13 사이를 탐색한다. 이때 와이파이는 하나 남았다.

4. 4의 인덱스 2와 13의 인덱스 5의 중간 값은 3이다. 와이파이가 하나 남았으므로 4부터 5까지의 거리와 5부터 13까지의 거리중 더 작은 것을 선택한다.

5. 값은 1이 나온다.

 

하지만 정답은 마지막 와이파이를 5가 아닌 9에 두어야 한다.

두 번째 풀이(답)

https://jiwonna52.tistory.com/76

백준, 공유기 설치(2110, java)

그렇다면 어떻게 풀어야 할까?

 

답은 최대한 거리를 벌려야 한다는 것에 있다.

 

최대한 간격을 벌려야 하므로 거리의 절반을 찾아 해당 간격만큼 와이파이를 얼마나 둘 수 있는지 확인한다. 그리고 만일 주어진 와이파이를 모두 사용해서 설치할 수 있으면 거리를 더 넓힌다. 중간에 break로 탈출하지 않는 이유는 집 간의 간격이 최대가 되어야 하므로 가능한 와이파이의 거리를 최대한 늘려줘야 하는 것이다.

 

예제를 보면서 생각해 보자.

집의 좌표를 정렬하면 [1, 2, 4, 8, 9] 이렇게 배열이 나온다.

 

일단 전체 거리를 구하기 위해서 (9-1)+1을 해준다.

전체 거리가 9이니 절반인 5를 기준으로 와이파이를 거리 최소 5만큼의 간격으로 놓았을 때 얼마나 놓을 수 있는지 계산해본다.

 

첫 번째 집에 와이파이를 놓았다고 가정한다. 첫 번째 집과 두 번째 집 사이의 거리는 1이라서 최소 거리 5보다 작아 와이파이를 놓지 못한다. 세 번째 집 또한 거리가 3이라 최소 거리보다 작아 놓을 수 없다. 네 번째 집은 어떠한가? 거리가 7이라서 와이파이를 놓을 수 있다(최소 거리인 5보다 크기 때문).

 

이렇게1과 8 총 2개 놓을 수 있는데, 우리가 놓아야 할 와이파이는 총 3개이므로 조건을 충족하지 못한다.

 

그러면 거리 5를 마지막 좌표로 두고 절반 값을 구한다. 이때 (1+5)/2는 3이므로 최소 거리는 3이 된다. 

이제 와이파이를 3 간격으로 놓을 때 얼마나 많이 놓을 수 있는지 확인해보자. 그렇다면 와이파이를 1, 4, 9 이렇게 놓을 수 있고 이때 와이파이 수 조건과 일치한다. 그렇다면 2보다 3이 더 큰 수이므로 와이파이를 놓을 수 있는 간격의 최대 중 최소 값은 3이 된다.

왜 이진탐색일까?

그 이유는 와이파이의 조건에 따라서 탐색할 범위가 달라지기 때문이다.

 

위의 예시를 다시 한 번 보자.

집은 [1, 2, 4, 8, 9] 위치에 있고 와이파이를 총 3개 놓아야 한다. 이때 와이파이의 간격이 최대가 되면 좋겠다.

 

10/2를 해서 mid값이 5가 나왔다. 그런데, 와이파이 수가 2라 조건인 3보다 더 작게 나온다. 한 번 생각해 보자. 거리를 더 늘려준다고 해서 와이파이의 수가 조건보다 크거나 같게 나올 수 있을까?

 

아니, 와이파이의 수는 조건보다 더 작아질 뿐 커지지는 않을 것이다. 오히려 거리를 좁혀서 가능한 와이파이 수를 늘려줘야 한다.

 

때문에 조건을 충족하지 않는 절반의 값은 굳이 계산할 필요가 없어 무시해도 괜찮다. 이는 즉, 이진탐색의 아이디어와 동일하기에 이진탐색을 사용해서 효율적으로 문제를 풀 수 있는 것이다.

코드

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.*;

public class Main {
    public static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input1 = br.readLine().split(" ");
        int N = Integer.parseInt(input1[0]);
        int C = Integer.parseInt(input1[1]);
        arr = new int[N];

        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(arr);
        int start = 1;
        int end = arr[N-1] - arr[0]  + 1;
        int mid = 0;

        while(end > start){
            mid = (start+end)/2;

            if(calPossible(mid) >= C){
                start = mid+1;
            }else{
                end = mid;
            }
        }

        System.out.println(end-1);
    }

    public static int calPossible(int length){
        int pre = 0;
        int count = 1;

        for(int i=1; i<arr.length; i++){
            if(arr[i] - arr[pre] >= length){
                pre = i;
                count++;
            }
        }

        return count;
    }


}