[BOJ][Java] 백준 1477번: 휴게소 세우기

문제 설명

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

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

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

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

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

 

문제 풀이

이 문제의 경우 기존의 이분탐색처럼 구간을 찾으려고 하면 한 가지 의문이 들게됩니다.

지속적으로 제일 작은 구간을 찾는 것에 대해 이분탐색을 구할 필요 없이 작은 구간을 찾아서 /2 해주면 되면 안되나?라는 의문인데요.

저 역시 이런 고민을 하다가 매번 작은 구간을 찾아서 나눠주는 작업은 효율성이 떨어질 것 같아서 고민하게 되었습니다.

 

<파라매트릭 서치(Parametric Search) 설명 블로그>

https://www.crocus.co.kr/1000

 

위의 링크 블로그를 참고하시면 파라매트릭 서치 기법 이해하는 데에 있어서 도움이 되실 겁니다!

 

이 문제는 파라매트릭 서치 방법을 통해 최소 휴게소별 길이를 설정하고 길이에 따라 휴게소를 설치하였을 때 나오는 개수에 따라 비교하는 문제입니다. 

 

예를 들어 200 700 800이고 L=800일 때 

mid = 250일 때는 0 200 450 700 800 이라서 1개 설치되고

mid = 100일 땐 0 100 200 300 400 450 550 650 700 800 총 10개가 설치됩니다.

 

따라서 251일 때 0 200 451 700 800 이며 M=1을 만족하고 최댓값인 251을 찾게 되는 것입니다.

 

풀이 코드

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

public class Main {
    private static int N, M, L;
    private static int[] rest;
    public static void main(String[] args) throws IOException{
        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());
        rest = new int[N+2];
        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++) rest[i] = Integer.parseInt(st.nextToken());
        rest[0] = 0; rest[N+1] = L;

        Arrays.sort(rest);

        for(int i=0; i<=N; i++) rest[i] = rest[i+1] - rest[i] - 1;

        System.out.println(binary_search());
    }

    private static int binary_search(){
        int left = 1, right = L;
        while(left <= right){
            int mid = (left+right)/2;
            if(restCnt(mid) <= M){
                right = mid-1;
            }else{
                left = mid+1;
            }
        }
        return left;
    }

    private static int restCnt(int res){
        int cnt = 0;
        for(int i=0; i<=N; i++)
            cnt += rest[i]/res;
        return cnt;
    }
}

 

<출처>

https://www.acmicpc.net/problem/1477

1477번: 휴게소 세우기