• 백준 2110번 공유기 설치 :: 마이구미
    알고리즘 풀이/이진 탐색 2018. 3. 16. 20:24
    반응형

    이 글은 백준 알고리즘 2110번 "공유기 설치" 를 풀이한다.

    풀이 방법으로는 이분(이진) 탐색을 사용한다.

    문제 링크 - https://www.acmicpc.net/problem/2110

    이분 탐색 - http://mygumi.tistory.com/72


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

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

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


    이 문제는 파라메트릭 서치 알고리즘을 적용한다고 알려져있다.

    사실상 단순히 이분 탐색의 응용 문제라고 생각하면 된다.


    문제가 원하는 것은 가장 인접한 두 공유기 사이의 거리가 최대이길 원한다.

    이것은 모든 공유기들의 사이 간격이 공평하게 설치되기를 바라는 것을 의미한다고 볼 수 있다.


    예를 들어, 공유기 사이의 최소, 최대 거리의 범위는 다음과 같다.


    Input - 1 2 4 8 9

    min => 1

    max => 9 - 1 = 8


    이러한 경우를 찾기 위해서는 순수하게 생각하면, 공유기간의 간격(min ~ max) 인 각 간격을 기준으로 모든 집 좌표들을 확인해보면 된다.


    2110번 공유기 설치

    하지만 좌표의 수의 최대값이 1000000000 이라서 시간 초과를 경험할 수 있다.

    즉, 단순한 탐색(O(n^2)) 으로는 해결 할 수 없다.

    시간을 줄이기 위해 우리는 이분 탐색을 사용할 수 있다.


    각 간격을 기준으로 일일이 확인하는 것이 아닌 이분 탐색의 방식을 이용하는 것이다.


    1. 특정 간격을 기준으로 가능한 위치에 공유기를 설치한다.
    2. 설치한 후에는 다음과 판단한다.
    3. 공유기 수가 더 설치되어야 한다면, 간격을 줄인다.
    4. 공유기 수를 줄여야한다면, 간격을 늘린다.


    위 과정을 반복하여 원하는 간격을 얻어낸다.


    Github - https://github.com/hotehrud/acmicpc/blob/master/algorithm/binarysearch/2110.java


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    private void solve() {
        int n = sc.nextInt();
        int c = sc.nextInt();
        int[] array = new int[n];
     
        for (int i = 0; i < n; i++) {
            array[i] = sc.nextInt();
        }
     
        Arrays.sort(array);
     
        int left = 1// 가능한 최소 거리
        int right = array[n - 1- array[0]; // 가능한 최대 거리
        int d = 0;
        int ans = 0;
     
        while (left <= right) {
            int mid = (left + right) / 2// 기준
            int start = array[0];
            int cnt = 1;
     
            // 간격(d) 를 기준으로 공유기 설치
            for (int i = 1; i < n; i++) {
                d = array[i] - start;
                if (mid <= d) {
                    ++cnt;
                    start = array[i];
                }
            }
     
            if (cnt >= c) {
                // 공유기의 수를 줄이자 => 간격 넓히기
                ans = mid;
                left = mid + 1;
            } else {
                // 공유기가 더 설치되어야한다. => 간격 좁히기
                right = mid - 1;
            }
        }
        System.out.println(ans);
    }
    cs


    반응형

    댓글

Designed by Tistory.