BOJ 1477 휴게소 세우기(Java)

문제 탐색하기

• 현재 고속도로 위 휴게소 개수 = N
• 더 세우려는 휴게소 수 = M
• 휴게소 짓는 조건은 다음과 같다.
  • 이미 휴게소 있는 곳에 또 못세운다.
  • 끝에도 못세운다.
  • 휴게소는 정수 위치에만 가능하다.
  • 휴게소가 없는 구간의 길이의 최댓값을 최소로 하려 한다.

---

고속도로의 길이가 1000이고, 현재 휴게소가 {2'00, 701, 800}에 있고, 휴게소를 1개 더 세우려고 한다고 해보자. 일단, 지금 이 고속도로를 타고 달릴 때, 휴게소가 없는 구간의 최댓값은 200~701구간인 501(701-200)이다. 하지만, 새로운 휴게소를 451구간에 짓게 되면, 최대가 251이 되어서 최소가 된다.

코드 설계하기

휴게소의 간격 을 기준으로 이분 탐색을 진행하고, 해당 간격만큼이 형성되도록 M개 휴게소를 생성할 수 있을때 이 간격의 최소값을 찾으면 된다.

구현 방법

• 휴게소 간 거리를 기준으로 이분 탐색을 진행한다.
  • 진행 전 배열은 정렬되어 있어야 한다.
• available() 에서 휴게소가 설치 가능한지 여부를 판정한다.

	private static boolean available(int mid) {  
        int cnt = 0;  
        for (int i = 1; i < list.size(); i++) {  
            int diff = list.get(i) - list.get(i - 1) - 1; // 휴게소 간 거리  
            cnt += diff / mid; // 간격을 휴게소 없는 구간 최댓값(후보)으로  나누면 들어갈 수 있는 휴게소 수  
        }  
        return cnt > M; // 지을 수 있는 휴게소 수가 지으려는 휴게소 갯수보다 많으면 참  
    } 

시간 복잡도

• 정렬 : O(N log N)
• 이진 탐색 : O(log L)
  • available 함수 호출: O(N)
• O(N log N + N log L)

문제의 조건에 의해 0 ≤ N ≤ 50, 1 ≤ M ≤ 100, 100 ≤ L ≤ 1,000 이므로 많아도 약 500회 정도의 연산이 일어난다. 따라서 무리 없이 연산이 가능하다.

정답 코드 (Java)

import java.io.*;  
import java.util.*;  
  
public class b1477 {  
    private static int N, M, L;  
    private static ArrayList<Integer> list;  
    public static void main(String[] args) throws Exception {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer st = new StringTokenizer(br.readLine());  
  
        N = Integer.parseInt(st.nextToken());  
        M = Integer.parseInt(st.nextToken());  
        L = Integer.parseInt(st.nextToken());  
  
        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);  
  
        // binary search  
        int left = 1, right = L;  
        while (left <= right) {  
            int mid = (left + right) / 2;  
            if (available(mid)) left = mid + 1;  
            else right = mid - 1;  
        }  
  
        System.out.println(left);  
    }  
  
    private static boolean available(int mid) {  
        int cnt = 0;  
        for (int i = 1; i < list.size(); i++) {  
            int diff = list.get(i) - list.get(i - 1) - 1; // 휴게소 간 거리  
            cnt += diff / mid; // 간격을 휴게소 없는 구간 최댓값(후보)으로  나누면 들어갈 수 있는 휴게소 수  
        }  
        return cnt > M; // 지을 수 있는 휴게소 수가 지으려는 휴게소 갯수보다 많으면 참  
    }  
}