[백준] 2110번 : 공유기 설치 - 자바(JAVA)

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

2110번: 공유기 설치

 

문제 해석

집 N개가 수직선 위에 존재하고 집 여러 개가 같은 좌표를 가지는 일은 없다.

공유기 C개를 설치하려고 하는데 한 집에는 공유기를 하나만 설치할 수 있다.

가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

집의 개수와 공유기의 개수가 주어질 때 두 공유기 사이의 최대 거리를 출력하라.

 

문제 풀이 전 설계

집의 개수가 20만개이며 공유기의 개수도 20만 개일 수 있습니다.

20만개 C(공유기의개수) 등으로 조합을 사용한 완전 탐색은 불가능해 보입니다.

 

우선 정렬을 먼저 하는것이 좋아 보입니다.

1 2 8 4 9가 입력 예시로 들어왔습니다.

 

정렬 후에는 1 2 4 8 9가 됩니다.

 

여기서 공유기를 3개를 설치해야 합니다.

이때는 가운데에 하나를 설치하고 양끝에 하나씩 설치하면 가장 먼 곳인 1, 4, 9에 설치했을 때 공유기 사이의 거리는 3이 됩니다.

 

조금 범위를 확장해보고 극단적인 예시를 들어보겠습니다.

1 2 3 4 5 100 200 300 400 500 600

 

여기서 공유기 5기를 설치해야 한다면 어떻게 해야 할까요?

처음에는 일정 간격을 두고 공유기를 설치하는 것이 좋다고 생각했습니다.

200 // 1,600 // 3, 400으로 설치한다면 공유기 사이의 거리는 2입니다.

하지만 100,200,300,400,500 이렇게 설치한다면 공유기 사이의 거리는 100입니다.

 

즉, 이로 인해 인덱스로 이 문제를 해결하고자 하면 안 될 것 같습니다.

 

좌표 기준으로 정렬 후 인덱스 대신에 공유기 사이의 간격을 기록하고 이 간격을 사용해야 할 것 같습니다.

 

그리고 이 간격이 큰 순서대로 한번 더 정렬을 합니다.

 

아까 1 2 3 4... 500 600의 예시로는

100 100 100 100 100 95 1 1 1 1입니다.

 

만약 공유기가 2개라면 모두 이를 모두 다 더한 값이 정답이 됩니다.

하지만 공유기가 3개라면... 4개라면... n 개라면의 일반화를 도출하지 못했습니다.

 

 

문제 풀이

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

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

 

입력값이 다음과 같이 주어졌습니다.

1 2 4 8 9

 

공유기 사이의 최소, 최대 거리의 범위는 min = 1, max = 8입니다.

 

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

 

하지만 집의 좌표가 10억까지 가능합니다.

 

만약 어떤 간격을 가지고 있을 것이라고 탐색할 때 그러면 O(N)만 하더라도 O(10억입니다)

 

 

이러한 간격을 판별할 때 일일이 확인하는 것이 아니라 이분 탐색의 방식을 이용합니다.

 

 

풀이

처음에 입력은 정렬된 순서로 주지 않기 때문에 정렬을 해서 위와 같이 만듭니다.

집 사이의 최대 거리는 9 - 1 = 8

집 사이의 최소거리는 2 - 1 = 1

이때 middle값은 1+8 = 9     9/2의 몫은 4이기 때문에 4입니다.

 

집마다 거리를 4 이상으로 놓고 공유기를 설치할 수 있는지 확인합니다.

입력 예시에서 공유기 개수를 3으로 줬기 때문에 위의 경우는 불가능합니다.

이제 최대는 middle보다 작은 3 최소는 1로 설정합니다

이제 middle은 1+3 = 4 / 2 = 2입니다.

 

집마다 거리를 2 이상으로 놓고 설치해보니 3개를 설치할 수 있습니다.

하지만 우리는 최대 거리를 찾아야 하기 때문에 일단 거리가 2는 가능하다를 기록하고 더 큰 거리에서 가능한지 확인합니다.

 

이제는 최소거리를 증가시켜 최소거리 3 최대는 3입니다.

 

거리를 3 이상으로 놓아도 위와 같이 공유기를 3개 설치할 수 있습니다.

즉 거리가 3일 때 최대입니다.

 

 

코드

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

public class Main_2110_공유기설치 {
    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());
        int C = Integer.parseInt(st.nextToken());
        int[] homes = new int[N];
        for(int i=0; i<N; i++){
            homes[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(homes);
        int min = Integer.MAX_VALUE;
        for(int i=1; i<N; i++){
            min = Math.min(min, homes[i]-homes[i-1]);
        }
        int max = homes[N-1] - homes[0];


        int result = 0;

        while(min <= max){
            int middle = (min + max) / 2;
            int start = homes[0];
            int count =1;

            for(int i=0; i<N; i++){
                if(homes[i] - start >= middle){
                    count++;
                    start = homes[i];
                }
            }

            if(count >= C){
                result = middle;
                min = middle+1;
            } else{
                max = middle-1;
            }
        }
        System.out.println(result);

    }
}

 

 

출처

https://devlog-wjdrbs96.tistory.com/267

백준 2110번 공유기 설치 (Java)