[Java] [백준 1477][이분 탐색, Parametric Search] 휴게소 세우기

문제

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

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

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

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

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

입력

첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. N은 100보다 작거나 같으며, M도 100보다 작거나 같다. L은 100보다 크거나 같고, 1000보다 작거나 같은 정수이다. 모든 휴게소의 위치는 중복되지 않으며, N+M은 L보다 작다. 둘째 줄에, 휴게소의 위치가 공백을 사이에 두고 주어진다.

출력

첫째 줄에 M개의 휴게소를 짓고 난 후에 휴게소가 없는 구간의 최댓값의 최솟값을 출력한다.

 

 

---

🌈 풀이 후기

• K번째 수와 동일하게 이분 탐색을 응용한 Parametric Search 문제입니다.
• 처음에 이 문제를 잘 이해하지 못했는데 아래 블로그 글을 보고 이해하게 되었습니다. 0~1000 사이에서 500이 조건을 만족한다면 0~499는 확인하지 않고 500~1000을 탐색하면 됩니다.

파라매트릭 서치(Parametric Search)

👩‍🏫 문제 풀이

알고리즘 - Parametric Search ( 이분탐색 유사)

• 휴게소의 거리이기 때문에 처음 0, 마지막 L을 추가로 넣어줍니다. 그리고 정렬한 뒤에 이분 탐색을 시작합니다.

• 휴게소 사이 거리가 Mid라고 했을때, 현재 세워진 휴게소 사이에 새로 끼워 넣을 수 있는 휴게소 수의 합을 체크해서 M보다 크다면 조건을 충족하기 때문에 더 넓은 범위에서 탐색합니다.

• 만약에 조건에 부합하지 않는다면 범위를 낮춰서 탐색합니다.

---

본 문제의 예시를 보면 다음과 같습니다.

 

mid: 400 sum: 0, L: 0 right: 800

⇒ 휴게소 거리를 400이라고 했을 경우, 세울 수 있는 휴게소 수는 0개이다. 조건을 충족하지 않기에 범위를 낮춰서 검사한다.

 

mid: 199 sum: 1, L: 0 right: 399

 

mid: 99 sum: 5, L: 0 right: 198

 

mid: 49 sum: 12, L: 0 right: 98

⇒ 휴게소 거리를 49라고 했을 경우, 세울 수 있는 휴게소 수는 12개이다. 따라서 조건을 충족하기 때문에 범위를 넓혀서 검사한다.

 

mid: 74 sum: 6, L: 50 right: 98

 

mid: 61 sum: 10, L: 50 right: 73

 

mid: 67 sum: 8, L: 62 right: 73

 

mid: 70 sum: 7, L: 68 right: 73

 

mid: 68 sum: 8, L: 68 right: 69

 

mid: 69 sum: 8, L: 69 right: 69

⇒ left에 +1을 하면 더이상 left가 right보다 작거나 같지 않기에 반복문을 빠져나간다.

 

package com.Boj.Day5;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

//이분 탐색 (Parametric search) 
public class BOJ_G5_1477_휴게소세우기 {
	static int N, M, L;
	static int[] rest;
	static int left, right;
	static int result = 0;

	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);

		binarySearch();
		System.out.println(left);
	}

	// 0 82 201 411 555 622 755 800
	// 휴게소 m개를 추가로 지었을 때, 각 휴게소 사이의 거리의 최대값이 d 이하가 되게 만들 수 있는가? => T / F
	// M개를 설치했을 때 각 휴게소끼리의 거리의 최대값을 mid라고 하자. 조건을 충족하는 최적의 mid를 찾아가는 방식이다.
	// 만약 400일때 조건을 충족한다면 0~399는 볼필요도 없다. 401부터 최대값을 찾아나간다.
	private static void binarySearch() {
		left = 0;
		right = L;

		while (left <= right) {
			int mid = (left + right) / 2;
			int sum = 0;

			for (int i = 1; i < N + 2; i++)
				// 휴게소 사이 거리가 mid라고 했을때, 현재 세워진 휴게소 사이에 새로 끼워 넣을 수 있는 휴게소 수.
				sum += (rest[i] - rest[i - 1] - 1) / mid;
			
//			System.out.println("mid: "+mid+" sum: "+sum+", L: "+left+" right: "+right);
			// 현재 mid의 거리 차이가 가능하다면 => 더 최대값을 찾기 위해 더 넓은 범위 탐색. 
			if (sum > M)
				left = mid + 1;

			// 더 적게 세워야 하면 간격을 줄인다.
			else
				right = mid - 1;

		}

	}

}