[백준] 1477번 휴게소 세우기 (JAVA)

문제

- 현재 고속도로에 휴게소가 N개 있음

- 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지로 주어짐

- 지금 휴게소를 M개 더 세우려고 함(반드시 모두 지어야 함)

- 이미 휴게소가 있는 곳에 휴게소를 또 세울 수 없고, 고속도로의 끝에 휴게소를 세울 수 없음

- 휴게소가 없는 구간의 길이의 최댓값을 최소로 하려고 함

- 휴게소가 없는 구간의 최댓값의 최솟값 출력

 

해결방법

처음에는 휴게소가 없는 구간들을 정렬하고 큰 수부터 중간에다 휴게소를 세우는 방식으로 문제를 해결하려 했으나, 나머지 테케는 잘 통과했지만 첫 테케가 막혔다.. 

이분 탐색으로 문제를 해결하였는데, 휴게소 위치들을 리스트에 담아두고 휴게소 사이에 이분 탐색으로 구한 그 구간의 길이만큼씩 휴게소를 배치한다면 몇개를 배치할 수 있을지 계산하여 문제를 해결할 수 있도록 하였다.

 

코드

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int L = Integer.parseInt(st.nextToken());
        List<Integer> list = new ArrayList<>();			// 휴게소 위치 리스트

        list.add(0);		// 출발 위치
        list.add(L);		// 고속도로 끝 위치

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i<N; i++) {
            list.add(Integer.parseInt(st.nextToken()));
        }

        Collections.sort(list);
		
        // 이분 탐색
        int left = 1;
        int right = L;

        while(left <= right) {
            int mid = (left + right) / 2;
            int count = 0;
            // 휴게소 사이에 mid 길이만큼 거리에 휴게소를 세운다면 몇개의 휴게소를 세울 수 있을지 계산
            for(int i = 1; i<list.size(); i++)
                count += (list.get(i) - list.get(i-1) - 1) / mid;
            // 세울 수 있는 휴게소 개수에 따라 범위 재조정
            if(count > M) left = mid + 1;
            else right = mid - 1;
        }

        System.out.println(left);
    }
}