백준 1477 [자바] java 휴게소 세우기

문제 링크: https://www.acmicpc.net/problem/1477

1477번: 휴게소 세우기

 

▶문제

다솜이는 유료 고속도로를 가지고 있다. 다솜이는 현재 고속도로에 휴게소를 N개 가지고 있는데, 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지로 주어진다. 다솜이는 지금 휴게소를 M개 더 세우려고 한다.

다솜이는 이미 휴게소가 있는 곳에 휴게소를 또 세울 수 없고, 고속도로의 끝에도 휴게소를 세울 수 없다. 휴게소는 정수 위치에만 세울 수 있다.

다솜이는 이 고속도로를 이용할 때, 모든 휴게소를 방문한다. 다솜이는 휴게소를 M개 더 지어서 휴게소가 없는 구간의 길이의 최댓값을 최소로 하려고 한다. (반드시 M개를 모두 지어야 한다.)

예를 들어, 고속도로의 길이가 1000이고, 현재 휴게소가 {200, 701, 800}에 있고, 휴게소를 1개 더 세우려고 한다고 해보자.

일단, 지금 이 고속도로를 타고 달릴 때, 휴게소가 없는 구간의 최댓값은 200~701구간인 501이다. 하지만, 새로운 휴게소를 451구간에 짓게 되면, 최대가 251이 되어서 최소가 된다.

---

▶입력

첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다.

---

▶출력

첫째 줄에 M개의 휴게소를 짓고 난 후에 휴게소가 없는 구간의 최댓값의 최솟값을 출력한다.

---

▶해설

휴게소 간격중에 가장 큰 값을 가장 작게 만들면 되는 문제입니다.

 

처음에는 휴게소 사이의 값을 정렬해서 가장 큰 값들 먼저 2로 나눠서 설치하면 풀리겠는데? 하고 시도해봤습니다.

하지만 모든 경우의 수를 충족시키진 못했습니다.

 

그래서 거리에 초점을 맞춰 이분 탐색으로 시도했습니다.

 

left = 1 (거리가 0인 것은 굳이 신경쓸 필요가 없기 때문)

right = l-1 (거리가 l인 것은 존재할 수 없기 때문)

 

dis = (left+right)/2입니다. (휴게소 간격)

 

 

(arr[i]-arr[i-1]-1)/dis -> 휴게소 사이에 dis의 거리를 만족하는 휴게소를 몇 개 설치가 가능한지 확인합니다.

1~n+1까지 확인합니다. (고속도로 시작점 0과 끝지점 l이 포함되기 때문)

 

개수가 m개를 넘을 때 참을 반환합니다. 더 큰 간격이 필요하므로 left = dis+1 됩니다.

개수가 m개와 작거나 같을 때 거짓을 반환합니다. 더 작은 간격이 필요하므로 right=dis-1 됩니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int n, m, l;
    static int[] arr;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        l = Integer.parseInt(s[2]);
        arr = new int[n+2];
        arr[0]=0;
        arr[n+1]=l;
        makeArr(br);
        int result = solve();

        System.out.println(result);
    }

    private static int solve() {
        Arrays.sort(arr);
        int left = 1;
        int right = l-1;
        while (left <= right) {
            int dis = (left + right) / 2;
            if (make_store(dis)) {
                 left = dis + 1;
            } else {
                 right = dis - 1;
            }
        }
        return left;
    }
    private static boolean make_store(int dis){
        int count=0;
        for(int i=1; i<=n+1; i++){
            count+=(arr[i]-arr[i-1]-1)/dis;
        }
        if(count>m){
            return true;
        }
        else{
            return false;
        }
    }

    private static void makeArr(BufferedReader br) throws IOException {
        String[] s1 = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i+1] = Integer.parseInt(s1[i]);
        }
    }
}