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

목차

문제 : boj1477

 

 

필요 알고리즘

• 매개 변수 탐색 (parametric search), 이분 탐색 (binary search)
  
  • 이분 탐색을 이용한 매개 변수 탐색으로 풀 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  2년전에 못풀었다고 되어 있는데, 이번엔 어렵지 않게 풀었다. 발전하긴 한 것 같아서 기분 좋았다.

 

  최소가 되는 구간을 직접 찾으려면 상당히 난감해진다. 그리디처럼 구간이 크다고 무조건 세운다?! 어쩌면 될 수도 있겠지만, 몇 개 세울지, 세우다보면 다른 구간이 가장 큰걸로 바꿀텐데 그건 어떻게 처리할지 등등 너무 복잡해진다.

 

  그러니 약간 생각을 바꿔서, "M개 이하의 휴게소를 더 지었을 때 휴게소가 없는 구간의 길이가 'X'이하로 가능한가?" 를 생각해보자. 이 경우엔 생각보다 간단하다.

 

  N개의 구간에 대해, 사이의 구간의 길이가 GAP이라 해보자. 그럼 'X' 이하로 하려면 휴게소가 몇 개 더 필요할까? '(GAP-1)/X'개를 해당 구간에 더 세우면 된다. 예를들어서 이미 휴게소가 1이랑 6에 있었다고 해보자. 구간의 길이가 2이하가 되게 하려면 (6-1-1)/2 = 2개를 더 세우면 된다. 3번과 5번 구간에 휴게소를 추가로 세우면 될꺼다. 그럼 M에서 2개가 빠지게 되고, 최종적으로 M이 0이상이라면 'X' 이하로 세울 수 있다는 얘기이다.

 

  '반드시 M개를 모두 지어야 한다.'는 신경쓸 필요가 없다. 어차피 현재 찾는게 'X' 이하로 가능하냐이므로, M이 남았다면 그냥 아무대나 세워도 'X' 이하로 가능하냐는 부분은 바뀌지 않는다.

 

  자 그럼 이제 'X'값만 적절히 정해주면 된다. 이 부분에서 매개 변수 탐색을 쓰면 효율적이다.

 

코드 : github

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int len = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int[] arr = new int[n+2];
        arr[n+1] = len;
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);

        int s = 1, e = len/m+1;
        while (s <= e) {
            int mid = (s+e)/2;
            if (possible(arr, m, mid)) {
                e = mid-1;
            } else {
                s = mid+1;
            }
        }
        System.out.println(s);
    }

    private boolean possible(final int[] arr, final int m, final int want) {
        int remain = m;
        for (int i = 1; i < arr.length && remain >= 0; i++) {
            int gap = arr[i] - arr[i-1];
            if (gap <= want) continue;

            remain -= (gap-1)/want;
        }

        return remain >= 0;
    }
}