[Algorithm] 공유기 설치

문제

도현이의 집 N개가 수직선 위에 있다. 각 집의 좌표는 같은 좌표를 가지지 않는다.

언제 어디서나 와이파이를 즐기기 위해 집에 공유기 C개를 설치하려고 한다.

최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기 하나만 설치할 수 있고,

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

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

 

풀이

해당 문제는 공유기가 설치되는 거리를 찾아야 한다.

1. 공유기 설치되는 집을 조합으로 뽑아 각각의 거리를 확인한다?

2. 공유기 설치되는 거리를 줄여나가면서 몇개가 설치되는지 확인한다?

1번보다는 2번을 알고리즘으로 푸는데 효율적으로 보인다. (조합하고, 연산하고 반복하면 더 많은 소모가 필요할 것 같음.) 탐색하는데 있어서 거리를 이진트리로 탐색한다.

 

가장 작은 거리 (적어도 1), 가장 큰 거리 (왼쪽 끝과 오른쪽 끝 집의 거리) 를 정한다.

        int start = 1;
        int end = arr[n-1] - arr[0];

그리고 각 거리의 중간 값을 찾아 1번 집부터 해당 거리로 설치하면 몇개가 설치 가능한지 확인한다.

 

설치할 수 있는 개수가 많다면 거리를 늘린다. 설치할 수 있는 개수가 부족하다면 거리를 줄인다.

설치할 수 있는 개수를 확인하는 방법은 처음 집에서 거리만큼 더한 값이 그 다음 집에 닿는다면 카운트하고,

그 다음 집에서 거리만큼 더한 값이 그그 다음집에 닿는지 확인하고 카운트를 반복한다.

            int mid = (start + end) / 2;
            int tmp = arr[0];
            int cnt = 1;
            for (int i = 1; i < n; i++) {
                if (arr[i] >= tmp + mid) {
                    cnt++;
                    tmp = arr[i];
                }
            }

 

전체소스코드

import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

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

        Arrays.sort(arr);

        int start = 1;
        int end = arr[n-1] - arr[0];
        int result = 0;
        while (start <= end) {
            int mid = (start + end) / 2;
            int tmp = arr[0];
            int cnt = 1;
            for (int i = 1; i < n; i++) {
                if (arr[i] >= tmp + mid) {
                    cnt++;
                    tmp = arr[i];
                }
            }

            if (cnt >= m) {
                start = mid + 1;
                result = mid;
            } else {
                end = mid - 1;
            }

        }
        
        System.out.println(result);
        
    }
        
}