[알고리즘] 백준 > #2110. 공유기 설치

재밌다 재밌다.........

문제링크

백준 #2110. 공유기 설치

풀이방법

"인접한 두 공유기 사이의 거리"를 편의상 D라고 할게용

D는 유일한 값을 갖지 않는 값이에요. 범위를 갖고있죠! 그래서 문제에서도 D의 최대값을 물어보고 있죠?? 그래서 그 범위를 점점 좁혀서 구하기로 했습니다.

범위를 좁히기 위해 이분탐색을 사용한 Parametric Search를 구현했습니다. 즉, 이분탐색으로 값을 얻고 그 값을 툭툭 던져보면서 만족하냐/그렇지 않냐를 판별하고 범위를 좁히는 거죵. 이렇게 구현하면 시간복잡도는 O(NlogX)가 되겠네요!

+) 이 알고리즘을 사용할 때 사람들은 left - right 값이 1보다 작을때 탐색을 멈추더라구요 근데 저는 이게 너무 헷갈려요. 그래서 [구한 범위 내 가장 작은 D값, 아는 값 중 D를 만족하지 않는 가장 작은 거리) 이렇게 두 값을 이용했습니다.

따라서, 두 값은 최초에 다음과 같이 초기화를 했습니다.

• 구한 범위 내 가장 작은 D값 = 1 (최소 두개의 공유기를 갖고 있고, 집의 위치는 모두 다르기 때문)
• 아는 값 중 D를 만족하지 않는 가장 작은 거리 = 가장 먼 두 집 사이의 거리 + 1

코드

public class RouterInstallation {
    static int[] homeLocations;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int c = sc.nextInt();

        homeLocations = new int[n];
        for (int i = 0; i < n; i++) {
            homeLocations[i] = sc.nextInt();
        }

        Arrays.sort(homeLocations);

        int smallestPossibleD = 1;
        int smallestImpossibleD = homeLocations[n - 1] - homeLocations[0] + 1;

        int midD = (smallestPossibleD + smallestImpossibleD) / 2;

        while ((smallestPossibleD != midD) && (smallestImpossibleD != midD)) {
            if (isPossibleDistance(midD, n, c)) smallestPossibleD = midD;
            else smallestImpossibleD = midD;

            midD = (smallestPossibleD + smallestImpossibleD) / 2;
        }

        System.out.println(smallestPossibleD);
    }

    private static boolean isPossibleDistance(int d, int n, int c) {
        int count = 1;

        int tempPos = homeLocations[0];

        for (int i = 1; i < n; i++) {
            if (homeLocations[i] - tempPos >= d) {
                tempPos = homeLocations[i];
                count++;
            }
        }

        if (count < c) return false;
        else return true;
    }
}