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

설명

N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ......, xN의 좌표를 가지며, 마구간간에 좌표가 중복되는 일은 없습니다.

현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다. 각 마구간에는 한 마리의 말만 넣을 수 있고,

가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다.

C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 출력하는 프로그램을 작성하세요.

 

입력

첫 줄에 자연수 N(3<=N<=200,000)과 C(2<=C<=N)이 공백을 사이에 두고 주어집니다.

둘째 줄에 마구간의 좌표 xi(0<=xi<=1,000,000,000)가 차례로 주어집니다.

 

출력

첫 줄에 가장 가까운 두 말의 최대 거리를 출력하세요.

 

예시 입력 1 

5 3
1 2 8 4 9

 

예시 출력 1

3

 

문제 이해

 

주어진 마구간에 C마리의 말을 배치하여, 가장 가까운 두 말 사이의 거리가 최대가 되도록 해야 하는 최적화 문제이다. 

이 문제도 문제 제목에 결정 알고리즘이 포함되어 이진 탐색을 이용해 풀어나가면 될 거 같당

// 가장 가까운 두 말의 거리가 최대가 되도록
// C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 출력
// ★ ★ ☆ ★ ☆ ☆ ☆ ★ ★
// ★      ★            ★

 

문제 해결

 

 

Scanner in = new Scanner(System.in);
int N = in.nextInt();
int C = in.nextInt();
int[] stables = new int[N];

for(int i = 0; i < N; i++){
    stables[i] = in.nextInt();
}
Arrays.sort(stables);

• N에 마구간의 개수, C에 말의 개수를 입력 받는다.
• stables 배열은 각 마구간의 위치를 입력받고, 
• 이 배열을 오름차순으로 정렬해둔다.

 

int lt = 1;
int rt = stables[N-1] - stables[0];
int answer = 0;

• 앞 문제와 같이 값이 존재할 수 있는 범위 안에서 이진 탐색을 진행하는데 이 때의 lt, rt를 정해줘야 한다.
• lt는 이진 탐색의 최소 거리를 의미하고 이 때는 말끼리의 거리의 최소를 의미하기에 1이 된다
• rt는 가능한 최대 거리로 마구간 위치의 최소와 최대의 차이가 된다.
• 계산된 최대 거리를 저장할 answer 변수를 만들어주고 0으로 초기화시켜준다.

 

while(lt <= rt) {
    int mid = (lt + rt) / 2;
    if(canDeployHorses(stables, C, mid)) {
        answer = mid; // 마구간에 말을 배치할 수 있으면 답을 업데이트하고 최소 거리 증가
        lt = mid + 1;
    } else {
        rt = mid - 1; // 마구간에 말을 배치할 수 없으면 최소 거리 감소
    }
}

• 이제 범위가 정해졌으니 이진 탐색을 진행하면 된다.
• canDeployHorses 함수를 사용하여 현재 mid 거리로 말들을 배치할 수 있는지 확인한다. 가능하면 lt를 증가시켜 더 큰 거리를 탐색하고, 그렇지 않다면 rt를 감소시켜 거리를 줄인다.

 

private static boolean canDeployHorses(int[] stables, int C, int minDist) {
    int count = 1; // 첫 번째 말은 항상 첫 번째 마구간에 배치
    int lastPos = stables[0]; // 마지막으로 말을 배치한 마구간의 위치

    for (int i = 1; i < stables.length; i++) {
        if (stables[i] - lastPos >= minDist) {
            count++; // 새로운 말을 배치할 수 있다면 카운트 증가
            lastPos = stables[i]; // 마지막 위치 업데이트
            if (count >= C) return true; // 모든 말을 배치할 수 있으면 true 반환
        }
    }

    return false; // 모든 말을 배치할 수 없으면 false 반환
}

• 주어진 minDist 거리로 말들을 배치할 수 있는지 확인하는 canDeployHorses 함수를 만들어준다.
• 첫 번째 말은 항상 첫 번째 마구간에 배치한다. (그래야 일단 최대 거리가 가능해지므로) 그 후, 주어진 최소 거리 이상일 때만 새로운 말을 다음 마구간에 배치한다.
• count 변수는 배치된 말의 수를 나타내고, 모든 말을 배치할 수 있으면 true를, 그렇지 않으면 false를 반환한다.

 

최종 코드

 

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

public class P10_마구간정하기 {
    public static void main(String[] args) {
        // 가장 가까운 두 말의 거리가 최대가 되도록
        // C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 출력
        // ★ ★ ☆ ★ ☆ ☆ ☆ ★ ★
        // ★      ★            ★

        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int C = in.nextInt();
        int[] stables = new int[N];

        for(int i = 0; i < N; i++){
            stables[i] = in.nextInt();
        }
        Arrays.sort(stables);

        int lt = 1;
        int rt = stables[N-1] - stables[0];
        int answer = 0;

        while(lt <= rt) {
            int mid = (lt + rt) / 2;
            if(canDeployHorses(stables, C, mid)) {
                answer = mid; // 마구간에 말을 배치할 수 있으면 답을 업데이트하고 최소 거리 증가
                lt = mid + 1;
            } else {
                rt = mid - 1; // 마구간에 말을 배치할 수 없으면 최소 거리 감소
            }
        }

        System.out.println(answer);
    }

    private static boolean canDeployHorses(int[] stables, int C, int minDist) {
        int count = 1; // 첫 번째 말은 항상 첫 번째 마구간에 배치
        int lastPos = stables[0]; // 마지막으로 말을 배치한 마구간의 위치

        for (int i = 1; i < stables.length; i++) {
            if (stables[i] - lastPos >= minDist) {
                count++; // 새로운 말을 배치할 수 있다면 카운트 증가
                lastPos = stables[i]; // 마지막 위치 업데이트
                if (count >= C) return true; // 모든 말을 배치할 수 있으면 true 반환
            }
        }

        return false; // 모든 말을 배치할 수 없으면 false 반환
    }

}