★★마구간 정하기(결정알고리즘)

 

import java.util.*;

public class Main {
    
    public int count(int[] arr, int dist) {
        //말의 마릿수
        int cnt = 1;
        //배치한 위치
        int ep = arr[0];
        
        for(int i = 1; i < arr.length; i++) {
            if(arr[i]-ep >= dist) {
                cnt++;
                ep=arr[i];
            }
        }
        return cnt;
    }
    
    public int solution(int n,int c, int[] arr) {
        int answer = 0;
        //mid를 가장 가까운 두 말의 거리로 배치시킨다.
        //더 좋은 답이 있다면 좁혀나간다.
        Arrays.sort(arr);
        int lt = 1;
        int rt = arr[n-1];
        while(lt<=rt) {
            int mid = (lt+rt)/2;
            if(count(arr ,mid) >= c) {
                answer=mid;
                lt = mid+1;
            } else rt = mid-1;
        }
        
        return answer;
    }

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

import java.util.*;

class Main {
    static int n,m;
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);

        n = kb.nextInt();
        m = kb.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }
        System.out.println(solution(m, arr));
    }

    private static int solution(int m, int[] arr) {
        int answer = 0;

        Arrays.sort(arr);
        //가장 두말의 최대 거리를 결정해놓고 이분탐색
        //최소 거리
        int start = 1;
        //최대 거리
        int end = arr[n-1]-arr[0];

        while(start<=end) {
            int mid = (start+end)/2;
            System.out.println("mid : " + mid);
            //해당 거리로 m마리의 말을 충분치 배치했으면 거리 더 늘려봐
            if(count(mid, arr) >= m) {
                start = mid + 1;
                answer = mid;
            }
            //배치 못했으면 두 말의 거리를 더 줄여봐
            else {
                end = mid - 1;
            }
        }

        return answer;
    }

    private static int count(int mid, int[] arr) {
        int count = 1;

        //첫번째 말은 무조건 배치
        int ep = arr[0];

        for(int i = 1; i < n; i++) {
            //해당 거리로 배치가 가능하면
            System.out.println("dis: " + (arr[i]-ep));
            if(arr[i]-ep >= mid) {
                count++;
                ep = arr[i];
            }
        }
        System.out.println("count : " + count);
        return count;
    }


}

이 문제도 왜 이분 검색으로 풀 수 있는지를 알아야한다.

가장 가까운 두 말의 최대거리를 mid로 두고 좁혀나갈 것임

lt = 1로 두고 rt는 9-1이 맞으나 그냥 마지막값으로 둬도 무방.

ep는 직전에 말을 배치한 좌표

배치된 말의 마릿수 count 메서드를 정의해서 count에 따라 탐색 범위를 결정할 수 있도록 할 것

count = 3이면 해당 거리로 말을 배치할 수 있다. (최대 거리인지는 더 탐색해봐야 암)

 

첫번째는 두 말의 최대거리를 1+9/2 = 5로 설정한다고 했을 때 이다.

여기서는 첫번째 말을 무조건 먼저 두는게 유리하므로 ep = arr[0] 으로 초기화한다. count = 1

나머지 말들과 ep 변수에 있는 말의 좌표를 비교한다.

5라는 거리로 2번째 마구간 배치 가능한가? -> arr[1]-ep >= dist 인가? 2-1 >= 5 두번째 마구간은 배치 불가능

5라는 거리로 3번째 마구간 배치 가능한가? -> arr[2]-ep >= dist 인가? 4-1 >= 5 세번째 마구간도 배치 불가능

5라는 거리로 4번째 마구간 배치 가능한가? -> arr[3]-ep >= dist 인가? 8-1 >= 5 네번째 마구간은 배치 가능

count = 2가 되고 ep = 8

5라는 거리로 5번째 마구간 배치 가능한가? -> arr[1]-ep >= dist 인가? 9-8 >= 5 두번째 마구간은 배치 불가능

2 개의 마구간 밖에 배치되지 않았으니 최대 거리가 5보다 낮아야 한다 -> 왼쪽 탐색해야함

 

두번째는 두 말의 최대거리를 1+4/2 = 2로 설정한다고 했을 때 이다.

여기서도 ep = arr[0] 이고 count = 1로 시작

위와 동일하게 말의 좌표를 비교한다.

2라는 거리로 2번째 마구간 배치 가능한가? -> arr[1]-ep >= dist 인가? 2-1 >= 2 두번째 마구간은 배치 불가능

2라는 거리로 3번째 마구간 배치 가능한가? -> arr[2]-ep >= dist 인가? 4-1 >= 2 세번째 마구간 배치 가능

2라는 거리로 4번째 마구간 배치 가능한가? -> arr[3]-ep >= dist 인가? 8-4 >= 2 네번째 마구간 배치 가능

2라는 거리로 5번째 마구간 배치 가능한가? -> arr[4]-ep >= dist 인가? 9-8 >= 2 다섯번째 마구간은 배치 불가능

최대 거리를 2라고 했을 때 배치가 가능해진다. answer 변수에 현재 까지의 최대 거리인 2를 넣기

3개의 마구간 배치가능하니 최대 거리가 2보다 높은 것도 탐색해본다. -> 오른쪽 탐색

 

세번째는 두 말의 최대거리를 2+4/2 = 3으로 설정한다고 했을 때 이다.

ep = arr[0] , count = 1

3이라는 거리로 2번째 마구간 배치 가능한가? -> arr[1]-ep >= dist 인가? 2-1 >= 3 두번째 마구간은 배치 불가능

3이라는 거리로 3번째 마구간 배치 가능한가? -> arr[2]-ep >= dist 인가? 4-1 >= 3 세번째 마구간은 배치 가능

3이라는 거리로 4번째 마구간 배치 가능한가? -> arr[3]-ep >= dist 인가? 8-4 >= 3 두번째 마구간도 배치 가능

3이라는 거리로 5번째 마구간 배치 가능한가? -> arr[3]-ep >= dist 인가? 9-8 >= 3 두번째 마구간도 배치 불가능

 

거리를 3으로 설정했을 때 두 말의 최대거리가 된다.