백준 - 1477 휴게소 세우기 - Java

백준 휴게소 세우기 문제를 풀어보았다. 이분탐색과 비슷하지만 조금 다른 파라매트릭 서치라는 것을 배울 수 있어 정리한다.

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

1477번: 휴게소 세우기

풀이 시간: 40분

---

문제 설명

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

• 고속도로에 기존 휴게소가 있고, 휴게소 간 거리를 줄이기 위해 휴게소를 더 세운다
• 더 세우려는 휴게소의 개수 m개를 세웠을 때 휴게소 간 거리의 최댓값이 최소가 되도록 세우자
• 제한사항을 보면 크게 문제될 것으로 보이지 않고, 휴게소의 위치 범위만 생각

---

문제 풀이

예제를 보면서 풀이를 생각해보았다.

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

휴게소의 위치들이 주어지고, 그 사이사이에 휴게소를 더 지어서 휴게소 간의 거리를 줄여나가면 된다.

이러한 경우는 최소거리가 되는 값을 찾는 것이기 때문에 이분탐색 알고리즘으로 mid를 찾아나가면 되겠다라고 생각을 했다.

 

• 현재 설치된 휴게소  사이 거리를 구해 기록한다.
• 고속도로의 총길이 내의 값으로 mid를 설정하고, 휴게소 사이 거리가 mid 보다 크면 그 사이에 휴게소를 세운다
• 휴게소를 세운 개수가 m개이면서 mid가 최소가 되는 mid값을 찾자(lower bound)

탐색을 하면서 휴게소를 세울 수 있는지 없는 지를 판단하는 것이 바로

파라매트릭 서치라고 한다.

대부분의 블로그에서 이 블로그를 참고로 올려놨는데, 정말 정리를 잘해 주셔서 나도 기록해 놓는다.

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

파라매트릭 서치(Parametric Search)

휴게소 세우기 문제에선 파라매트릭 서치를 하기 위해 휴게소 사이 거리를 가지고 이분탐색을 진행한다.

 

다시 예제를 보고 한 번 풀어보자.

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

휴게소를 추가로 세울 수 있는 구간을 보면

1. 1 ~ 81에 휴게소를 세울 수 있다.
2. 83 ~ 200
3. 202 ~ 410
4. 412 ~ 554
5. 556 ~ 621
6. 623 ~ 754
7. 756 ~ 999

휴게소 사이 거리의 최댓값을 mid로 90이라고 생각해 보자

1번 구간에는 세울 수 없다.

2번 구간에는 1개 세워서 최댓값이 90이 되게 할 수 있다.

3번 구간에는 휴게소 간 거리를 90이 되게 2개를 세울 수 있다.

• (휴게소 사이 거리가 180이 넘으니까 적절히 2개 세우면 20 몇 짜리 거리인 휴게소가 있는 것)
• 201(휴게소) 291(휴게소) 381(휴게소) 411(휴게소)

4번 구간에는 1개

5번 구간에는 1개

7번 구간에는 2개

따라서, 추가 휴게소 설치는 7개로 조건을 만족한다.

하지만, 여기서 끝이 아니라, mid값을 더 줄여서 7개 설치가 가능한 조건들 중 거리가 가장 작은(mid) 

이분탐색 알고리즘에서 lower bound로 결괏값을 반환해야 한다.

---

풀이 코드

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

class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken()), l = Integer.parseInt(st.nextToken());
        int[] initRest = new int[n+2];    // 시작과 끝 지점을 추가
        initRest[0] = 0;
        initRest[n+1] = l;
        st = new StringTokenizer(br.readLine());
        int[] rest = new int[n+1];
        for(int i=1; i<=n; i++){
            initRest[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(initRest);
        for(int i=0; i<=n; i++){
            rest[i] = initRest[i+1] - initRest[i] -1;   // 휴게소간 길이
        }
        System.out.println(binarySearch(rest, m, 1, l)+"");

        br.close();
    }
    public static int binarySearch(int[] rest, int m, int start, int end){
        while(start<end){
            int mid = (start + end) / 2;
            if(cntRest(rest, mid) > m){    // 지을 수 있는 휴게소가 m보다 많으면 더 길게
                start = mid + 1;
            }
            else end = mid;
        }
        return end;
    }
    public static int cntRest(int[] rest, int mid){
        int cnt = 0;
        for(int i=0; i<rest.length; i++){
            cnt += rest[i] / mid;
        }
        return cnt;
    }
}

• 우선 입력받은 휴게소 위치를 휴게소 사이의 거리로 변환한다.

이분탐색

• start와 end는 휴게소를 세울 수 있는 위치가 1부터 L-1이기 때문에 1부터 L로 넣었다. 시작위치는 1인걸 알겠다만, 왜 마지막은 L-1이 아니라 L이냐면.. 사실 상관없다. start만 1을 해주면 된다.
  • 만약 start가 0이면 end가 계속 mid로 줄어들면서 1이 되었다고 치면 mid가 0이 되어 에러가 반환되기 때문에 start를 1로만 해주면 된다.
• 지을 수 있는 휴게소가 m보다 많으면 mid를 줄여나가며 m과 같은 경우를 찾아야 되는 것이 아닌가 생각할 수 있는데, mid가 최소가 되는 경우를 반환하는 lower bound라고 생각하면 된다.
  • 결국 start와 end는 같아져야 종료되며, 그 경계가 cntRest(rest, mid) == m이 된다

휴게소 개수 세기

• 위에서 설명했듯이 휴게소 사이 거리를 기록해 놓고 그 구간을 mid로 나눈 몫만큼 휴게소를 더 세울 수 있다
  • 휴게소 사이 최댓값만 관심이 있으니 나머지 짧은 길이는 신경 쓰지 않아도 된다

---

이분탐색에서 lower bound와 upper bound는 계속 헷갈린다.

upper bound이든, lower bound이든 결국 경곗값은 조건식이 == 될 때로 수렴되는 데 부등호가 조건보다 크냐 작냐에 따라 lower, upper를 판단한다.

start            mid                  end

|-----------------|-------------------|

부등호가 조건보다 크다라고 했을 경우엔 start가 앞으로 가면서 end와의 간격을 좁혀가며 mid값을 더 크게 잡아 조건식의 크다의 기준을 점점 줄여나가는 것이다. 우리는 조건식과 같을 때를 얻고 싶고 end = mid로 줄어들게 되는 것이다.

따라서,  반환 값이 조건식을 만족하는 가장 작은 값이 되는 것이다.

 

단순히 외운다기보다 문제에 따라서 조건식이나 부등호를 잘 활용해 보면 좋을 것 같다

이 문제에서는 휴게소를 더 많이 세우는 경우 mid를 크게 해서 휴게소를 줄이자 -> start = mid + 1

세울 수 있는 휴게소가 m개이거나 적네 -> mid를 작게 해서 휴게소 개수를 늘리자 -> end = mid

이렇게 되면 휴게소가 m개이면서 가장 작은 휴게소 사이 거리가 되고 끝나겠구나를 이해하고 수식하면 된다.

 

upper bound의 경우는 조건식에 같다를 넣어서 반대로 같은 값 중에 가장 큰 값을 찾는 것이 된다.

조건과 같은데도 start를 앞으로 이동하며 mid값을 키운다!