문제 탐색하기

입력 자료 정리

1. n은 세워진 휴게소의 개수, m은 세워야할 휴게소 개수, l은 고속도로 길이다
2. 이어서 n만큼의 입력값은 휴게소가 세워진 위치다.

해결방법 추론

1. 휴게소를 얼마만큼의 간격으로 설치할지가 관심이므로 이 간격을 이분탐색하면 된다.
2. 주의할점 고속도로에서 휴게소가 없는 간격은 처음지점부터 첫 휴게소까지의 간격과
   마지막 휴게소부터 고속도로 끝지점까지 간격이다
3. 따라서 휴게소 설치 위치에 0과 l도 추가해야한다
4. 휴게소의 간격은 1부터 l-1까지 될 수 있으므로 이점을 유의해서 이분탐색하자
5. 이때 휴게소가 없는 구간의 최댓값의 최솟값을 출력하라 했으므로
   left를 최소간격으로 출력하면 될 것이다

시간복잡도 계산

1. 시간복잡도는 O(n x logl)이다. 따라서 시간제한안에 문제를 해결할 수 있다.

코드 설계하기

입력값 상태 관리

1. 입력값은 리스트로도 관리할 수 있는데, 이번 풀이는 그냥 n+2크기의 배열선언 후,
   처음값와 마지막 지점에 값을 넣고 1부터 n까지 입력 값을 넣도록 하였다
2. 이후 배열을 오름차순 정렬해주며, 탐색의 범위인 left는 1, right는 l-1로 지정한다

구현 코드 설계

1. 이분탐색 동안 휴게소를 탐색하며, 휴게소간 간격을 구해준다
2. 간격안에 몇개의 휴게소를 세울 수 있는지 이분탐색 중간값으로 나눠서 더해준다
3. 만약 m보다 크다면 left 범위를 늘리고 작거나 같다면 right 범위를 줄인다
4. 이때, ans에 들어값은 m보다 큰 경우가 아니라 작거나 같은 경우인데,
   m보다 큰 경우는 모두 휴게소를 세울 수 있지만 이 간격이 휴게소가 없는 구간의
   최댓값은 아니라는 의밍다
5. right인 경우는 동일한 간격일 때 세울 수 없다는 의미지,
   아예 세울 수 없다는 의미는 아니다. 남은 휴게소를 동일하지 않게 세우면 가능하다
6. 따라서 m보다 작거나 같은 경우에 ans를 갱신해주면 된다

출력값 설계

1. 완성한 ans를 출력하면 정답이 된다

정답코드

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



public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int l = Integer.parseInt(st.nextToken());
        int[] arr = new int[n+2];
        st = new StringTokenizer(br.readLine());
        arr[0] = 0;
        arr[n+1] = l;
        for (int i = 1; i < n+1; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        int left = 1;
        int right = l-1;
        int ans = 0;
        while(left <= right){
            int mid = (left + right) / 2;
            int count = 0;
            for (int i = 1; i < n + 2; i++) {
                count += (arr[i] - arr[i-1]-1) / mid;
            }

            if(count > m){
                left = mid + 1;
            }else{
                right = mid -1;
                ans = mid
            }

        }
        bw.write(ans+"");

        br.close();
        bw.close();
    }
}

문제 링크

1477번 - 휴게소 세우기