BOJ 2110 - 공유기 설치

문제

 

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

2110번: 공유기 설치

 

• 수직선 위 N개의 집 (2 ≤ N ≤ 200,000)
• 각 집의 좌표 xi (0 ≤ xi ≤ 10억)
• 공유기 C개 (2 ≤ C ≤ N)

 

 

아이디어

집이 5개이고 공유기가 3개인 경우

 

C개의 공유기를 몇몇 집에 설치할 것인데 가장 인접한 공유기 사이의 거리를 최대가 되도록 설치할 것이다.

' 최대 ' 라는 키워드가 나왔으므로 이분탐색을 먼저 생각해보았다.

 

원래 문제

C개의 공유기를 설치했을 때, 가장 인접한 공유기 사이의 최대 거리는 얼마인가?

 

최대 인접 거리를 매개 변수 D로 설정 후 문제를 뒤집어서 Yes or No 문제로 바꾼다.

 

뒤집어서 만든 Yes or No 문제

두 공유기 사이 거리가 D일 때 공유기 C개를 설치할 수 있는가? Yes or No

Yes인 것 중 가장 큰 값이 정답이 될 것이다. 

 

 

Yes or No 문제 풀이

어떤 거리 D 만큼 거리를 둘 때, 공유기 C개를 설치할 수 있는 지 알기 위해서는 주어진 집들의 좌표를 정렬한 후에 제일 왼쪽 집부터 되는 대로 전부 설치해보는 방법을 사용한다. 

 

D가 1일 경우

1 2 4 8 9

최대 5개의 공유기를 설치할 수 잇다.

 

D가 2일 경우

1 4 8, 1 4 9, 2 4 8, 2 4 9

최대 3개의 공유기를 설치할 수 있다.

 

D가 3일 경우

1 4 8, 1 4 9 

최대 3개의 공유기를 설치할 수 있다.

 

이와같이 왼쪽부터 그냥 되는 대로 전부 설치해보면 어짜피 정렬이 된 상태라서 애초에 오른쪽 집으로 갈 수록 인접한 공유기의 거리가 짧아지기 때문이다. D만큼의 거리를 확보하기 위해서 제일 왼쪽집부터 설치해나가면서 가능한 공유기 설치 개수를 카운트한다.

 

 

시간 복잡도

• 왼쪽부터 차례대로 설치해서 확인하면 되기 때문에 Yes or No 문제를 푸는 데에는 O(N)의 시간이 걸린다.
• N개의 집들을 정렬하는 데에는 최대 O(N logN)의 시간이 걸린다.
• 이분탐색 진행 시 탐색 범위가 최대 1~10억이므로 최대 질문 수는 log10억이 돼서 O(log 10억0의 시간이 걸린다.
• 총 시간 복잡도는 O(N logN + N log 10억) 이므로 N의 최댓값이 20만이라서 2초안에 풀이가 가능하다.

 

구현

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N, C;
    static int[] home;

    static void init() 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());

        home = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            home[i] = Integer.parseInt(br.readLine());
        }
    }

    static void pro() throws IOException {
        // 집들의 좌표 정렬
        Arrays.sort(home);

        // 이분탐색
        int L = 1;
        int R = 1000000000;
        int ans = 0;

        while (L <= R) {
            int mid = (L + R) / 2;

            // Yes인 경우
            if (YesOrNo(mid)) {
                L = mid + 1;
                ans = mid;

            // No인 경우
            } else {
                R = mid - 1;
            }
        }

        bw.write(ans+" ");
    }

    // 거리가 D일 때 C개 만큼의 공유기를 설치할 수 있는가? Yes or No?
    private static boolean YesOrNo(int D) {
        // 제일 왼쪽집부터 설치
        int cnt = 1;
        // 마지막 설치 위치
        int last = home[1];

        // 왼쪽에서부터 설치 시작
        for (int i = 2; i <= N; i++) {
            // 마지막 설치 위치로부터 D만큼 떨어진 곳에 설치
            if (home[i] - last >= D) {
                cnt++;
                last = home[i];
            }
        }

        // Yes or No
        if (cnt >= C) {
            return true;
        } else {
            return false;
        }
    }

    public static void main(String[] args) throws IOException {
        init();

        pro();

        bw.close();
    }

}