[알고리즘] 백준 2110 공유기 설치 -이분탐색- 자바

www.acmicpc.net/problem/2110

2110번: 공유기 설치

 

 

백준 이분탐색 단계별 풀기에 있는 공유기 설치 문제를 풀어봤습니다.

 

처음에 문제가 이해가 잘 안갔는데 저랑 같은 생각을 한 분의 블로그를 통해 이해할 수 있었습니다. 감사합니다.

dundung.tistory.com/54

백준 2110 공유기 설치 Java

 

 

한 마디로 공유기의 거리 간격을 최대 몇으로 했을 때 C개의 공유기를 설치할 수 있냐는 문제입니다.

이 공유기의 설치의 기준 거리를 이분 탐색을 해주면 해결됩니다.

 

풀이는 다음과 같습니다..

    import java.util.Arrays;
    import java.util.Scanner;

    class Main {

        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int N = sc.nextInt(); //도현이의 집
            int C = sc.nextInt(); // 공유기 개수
            int[] house = new int[N];
            int answer = 0;
            for (int i = 0; i < N; i++) {
                house[i] = sc.nextInt();
            }
            Arrays.sort(house);
            int left = 1; //최소 길이
            int right = house[N - 1] - house[0];// 최대 길이
            while (left <= right) {
                int mid = (left + right) / 2; //공유기 거리 기준
                int prevHouse = house[0]; //첫 위치에 설치
                int count = 1; //공유기 설치 개수
                for (int i = 0; i < N; i++) {
                    int distance = house[i] - prevHouse;
                    if (distance >= mid) { //거리차가 기준보다 이상되야 설치 가능
                        count++;
                        prevHouse = house[i];
                    }
                }
                if (count >= C) { //공유기 설치가 더 많이 됬으니 간격을 넓혀서 줄여야함
                    left = mid + 1;
                    answer = mid;
                } else {
                    right = mid - 1;
                }
            }
            System.out.println(answer);
        }
    }

 

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!