백준 2110번: 공유기 설치[JAVA]

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

2110번: 공유기 설치

 

 

[정답 코드]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        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[] arr = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(arr);

        int result = 0;
        int left = 0;
        int right = arr[N - 1] - arr[0]; // 최대 간격

        while (left <= right) {
            int cnt = 1;
            int cur = arr[0]; // 첫 번째 집부터 시작

            int mid = (right + left) / 2; //공유기 설치의 최소 간격

            for (int i = 1; i < N; i++) { // 첫 번째집은설치했으니 두번째집부터 시작
                if (arr[i] - cur >= mid) {
                    cnt++;
                    cur = arr[i]; // 현재 바라보는 인덱스(커서)를 설치한 집으로 이동
                }
            }

            if (cnt >= C) { // 공유기간의 거리를 적당히 설정해서 최소 C개만큼 설치했을 경우
                result = mid;

                // 좀더 좋은 결과값을 찾기위해 간격을 넓혀본다
                left = mid + 1;
            } else {
                // 결과값을 찾기위해 간격을 좁힌다
                right = mid - 1;
            }
        }
        System.out.println(result);
    }
}

 

[설명]

공유기를 설치한 집과 다음 설치할 집과의 간격이 mid 이상일 경우에만 cnt를 1씩 증가시킨다. for문이 끝난 후 cnt 의 값이 C이상일 경우 좀더 최적의 해를 찾기위해 간격을 넓혀서 재탐색해본다. 우리는 최댓값을 찾는것이기 때문이다. cnt의 값이 C보다 적을 경우 간격을 좁혀 해를 재탐색한다.