이코테 - 공유기 설치 with JAVA

 

 

 

해결

이 문제를 해결하기 위해서는 공유기 설치 간격을 이분탐색으로 구하면 된다.

즉, 공유기 설치 간격을 정해서 입력받은 공유기의 수보다 공유기를 설치 못한다면 공유기 설치 간격을 줄이고

반대로, 입력받은 공유기 수와 같거나 더 많이 설치 가능하다면 공유기 설치 간격을 늘려가며 이분탐색을 진행한다.

 

예를 들어, 집은 1, 2, 4, 8, 9 에 위치하고 공유기는 3개를 설치하고 싶다고 가정하자.

집간 최소 간격은 1이고 최대 간격은 8이다.

따라서 start=1, end=8로 설정한다.

첫번째 mid= 4가 되고 이는 공유기 설치 간격은 4가 되는 것이다.

위 집들에 적용하면 1, 8에 설치 가능하다. 이는 공유기 3개보다 적으므로 설치 간격을 줄인다.

 

두번째로는 start=1, mid=2, end=3

위 집들에 적용하면 1, 4, 8에 설치 가능하다. 따라서 간격을 늘려 적용해본다.

 

세번째로는 start=3, mid=3, end=3

위 집들에 적용하면 1, 4, 8에 설치 가능하고 결과적으로 최대값은 3이되는 것이다.

 

 

 

 

 

코드

import java.util.*;

// 공유기 설치
public class Q3 {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        // 집의 수
        int n = sc.nextInt();

        // 공유기 수
        int c = sc.nextInt();

        // 집 위치 입력 받기
        List<Integer> houses = new ArrayList<>();
        for(int i=0; i<n; i++){
            houses.add(sc.nextInt());
        }

        // 집 정렬
        Collections.sort(houses);

        // 공유기 설치 간격
        // 최소 : 1, 최대 : 구하기
        int start = 1;
        int end = houses.get(n-1)-houses.get(0);
        int result = 0;

        while(start <= end){
            // mid : 현재 공유기 설치 간격
            int mid = (start+end)/2;
            // 공유기 설치 시작점
            int value = houses.get(0);
            // 공유기 설치 수
            int count = 1;
            // 공유기 설치
            for(int i=1; i<n; i++){
                // 집이 기준 집+지정한 공유기 설치간격보다 넓다면
                // 해당 집에 공유기 설치 후 기준 집 수정
                if(houses.get(i) >= value+mid){
                    value = houses.get(i);
                    count += 1;
                }
            }
            // 설치된 공유기 수가 입력받은 공유기 수보다 크다면 설치 가능
            // 따라서 간격을 늘려서 다시 이분탐색
            if(count >= c){
                start = mid+1;
                result = mid;
            }
            // 입력받은 공유기 수보다 작다면 설치 불가능
            // 따라서 간격을 줄여서 다시 이분탐색
            else{
                end = mid-1;
            }
        }

        // 결과 출력
        System.out.println(result);
    }
}