[백준 - 2110] 공유기 설치 - Java

문제 설명

 

2110번: 공유기 설치

 

접근 방법

해당 문제는 이분 탐색을 이용하여 해결할 수 있었습니다.

 

여기서 이분 탐색을 찾고자 하는 것은 가장 인접한 두 공유기 사이의 최대 거리입니다. 이때 이분 탐색을 위한 시작점(start)을 1로 두었는데, 이는 인접한 두 공유기 간의 거리가 최소일 경우이기 때문입니다. 또한 끝점(end)을 첫번째 집과 마지막 집 사이의 거리(좌표 차)로 두었는데, 이는 인접한 두 공유기 간의 거리가 최대일 경우이기 때문입니다.

 

        int n = Integer.parseInt(st.nextToken()), c = Integer.parseInt(st.nextToken());

        routers = new int[n];
        for (int i = 0; i < n; i++) {
            routers[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(routers);

        int start = 1, end = routers[n - 1] - routers[0], mid, result = 0;

 

이후 이분 탐색을 통해 시작점과 끝점의 중간점(mid)을 구해 가면서 mid 이상 떨어져있는 인접한 공유기들의 개수를 구하도록 했습니다. 이때 이 mid 이상 떨어져 있는 인접한 공유기들의 개수가 적어도 C개 이상 있으면 모든 공유기가 설치된 것으로 볼 수 있는데, 왜냐하면 문제에서 요구하는 것은 '가장 인접한'이기 때문에 나머지 인접한 공유들끼리는 적어도 mid 이상 되어야합니다. 따라서 조건을 충족하면 mid를 결과값에 반영(최대인지 확인)하고, 다시 시작점을 1을 늘려 mid 보다 더 큰 인접 거리를 충족 시킬 수 있는지 재탐색하도록 합니다.

 

        // ...

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

            if (count(mid, c)) {
                start = mid + 1;
                result = Math.max(result, mid);
            } else {
                end = mid - 1;
            }
        }

        System.out.println(result);
    }

    private static boolean count(int mid, int c) {
        int count = 1, lastRouter = routers[0];

        for (int router : routers) {
            if (router - lastRouter >= mid) {
                if (++count == c) {
                    return true;
                }

                lastRouter = router;
            }
        }

        return false;
    }

 

소스 코드(이분 탐색)

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

class Main {

    static int[] routers;

    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()), c = Integer.parseInt(st.nextToken());

        routers = new int[n];
        for (int i = 0; i < n; i++) {
            routers[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(routers);

        int start = 1, end = routers[n - 1] - routers[0], mid, result = 0;

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

            if (count(mid, c)) {
                start = mid + 1;
                result = Math.max(result, mid);
            } else {
                end = mid - 1;
            }
        }

        System.out.println(result);
    }

    private static boolean count(int mid, int c) {
        int count = 1, lastRouter = routers[0];

        for (int router : routers) {
            if (router - lastRouter >= mid) {
                if (++count == c) {
                    return true;
                }
                
                lastRouter = router;
            }
        }

        return false;
    }
}

 

(번외) 백트래킹을 활용한 소스 코드(시간 초과)

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

class Main {

    static int[] routers;
    static int n, c, result = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

        routers = new int[n];
        for (int i = 0; i < n; i++) {
            routers[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(routers);

        boolean[] installed = new boolean[n];
        install(installed, 0, 0);

        System.out.println(result);
    }

    private static void install(boolean[] installed, int depth, int count) {
        if (count == c) {
            getMaxDistance(installed);
            return;
        }

        if (depth == n) {
            return;
        }

        installed[depth] = true;
        install(installed, depth + 1, count + 1);
        installed[depth] = false;
        install(installed, depth + 1, count);
    }

    private static void getMaxDistance(boolean[] installed) {
        int index = 0, pos = 0;
        for (int i = 0; i < n; i++) {
            if (installed[i]) {
                index = i;
                pos = routers[i];
                break;
            }
        }

        int distance = Integer.MAX_VALUE;
        for (int i = index + 1; i < n; i++) {
            if (installed[i]) {
                distance = Math.min(distance, routers[i] - pos);
                pos = routers[i];
            }
        }

        result = Math.max(result, distance);
    }
}

 

참고자료

• https://www.acmicpc.net/problem/2110
• https://st-lab.tistory.com/277