[결정알고리즘] 10.마구간 정하기

<<풀이>>

 

결정 알고리즘을 활용해서 문제를 풀었다.

 

이 번 문제는 거리에 대해 가장 작은 거리 1과 최대 거리 9를 lt와 rt로 두고, mid = (lt + rt) / 2를 활용했다.

 

1 에서 9 사이에 정답이 무조건 있다는 전제가 깔려있기 때문이다.

 

이제 구한 mid로 실제 거리를 빼가면서 비교했는데, 우선 가장 첫번째 1 위치에 말을 두고 시작했다. 1에 두고 시작해야 공간확보에 유리하기 때문이다. 그다음 mid 보다 같거나 크면 중지하고 그 위치에 말을 뒀다. 그리고 1 위치에서 부터 거리를 구하던 것을 말을 둔 위치로 변경한 뒤 같은 작업을 반복했다.

 

그렇게 해서 나온 값이 넣을 수 있는 말이 실제 넣으려는 말의 수 보다 같거나 크면 그 값은 유력한 후보가 된다.

 

만약 크거나 같다면, mid 이하의 값은 무조건 되기 때문에 mid 아래는 무시한다. 그래서 lt를 mid + 1로 다시 초기화 시킨다.

 

이 과정을 lt > rt 되기 전까지 진행한다.

 

이 알고리즘의 핵심은 정렬된 값과 그 정렬된 값 안에 무조건 답이 있을 때 사용이 가능하다 !! 이점을 잘 기억해둬서 나중에 또 써먹자 ㅎㅎ

 

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

class Main{

    private int total(int[] arr, int mid) {
        int em = arr[0];
        int count = 1;
        for(int i = 1; i < arr.length; i++) {
            if(arr[i] - em >= mid) {
                count++;
                em = arr[i];
            }
        }
        return count;
    }
    private int solution(int n, int m, int[] arr) {
        Arrays.sort(arr);
        int rt = Arrays.stream(arr).max().getAsInt();
        int lt = Arrays.stream(arr).min().getAsInt();
        int answer = 0;
        while(lt <= rt) {
            int mid = (rt + lt) / 2;
             if(total(arr, mid) >= m) {
                 answer = mid;
                 lt = mid + 1;
            } else rt = mid - 1;
        }
        return answer;

    }



    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }

        System.out.println(T.solution(n, m, arr));
    }
}