백준 1477번: 휴게소 세우기 (JAVA)

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

1477번: 휴게소 세우기

문제

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

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

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

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

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

입력

첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다.

출력

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

제한

• 0 ≤ N ≤ 50
• 1 ≤ M ≤ 100
• 100 ≤ L ≤ 1,000
• 1 ≤ 휴게소의 위치 ≤ L-1
• N+M < L
• 모든 휴게소의 위치는 중복되지 않음
• 입력으로 주어지는 모든 수는 정수

 

---

 

풀이

parameteric search 문제 중 하나이다. 특별할 건 없는데, 살짝 처리가 까다로운 듯하다.

우선, int 배열에 휴게소 간 간격을 저장한다. 주의할 점으로는, 가장 위치가 작은 휴게소도 0까지 '휴게소가 없는 간격'이 있으며, 마찬가지로 가장 위치가 큰 휴게소도 L까지 '휴게소가 없는 간격'이 있다.

이후, int mid에 대해 매개 변수 탐색을 도는데, 기준을 '각 휴게소 간격 사이 mid마다 휴게소를 설치한다'로 둔다.

특정 구간에 대하여, 휴게소를 install개 설치했다면, 해당 구간에서 최대 간격은 (간격+install-1)/install이 된다.

이후 설치한 휴게소가 M개 이하가 되는 mid 값 중 최대를 찾으면 된다.

 

 

코드

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

public 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());
		int M = Integer.parseInt(st.nextToken());
		int L = Integer.parseInt(st.nextToken());
		int[] rests = new int[N+2];
		st = new StringTokenizer(br.readLine());
		rests[0] = 0;
		for (int i = 1; i <= N; i++) {
			rests[i] = Integer.parseInt(st.nextToken());
		}
		rests[N+1] = L;
		Arrays.sort(rests);
		
        // 간격을 저장하는 배열
		int[] gap = new int[N+1];
		int end = 0;
		for (int i = 0; i <= N; i++) {
			gap[i] = rests[i+1] - rests[i];
			if (gap[i] > end) end = gap[i];
		}
		int start = 1;
		
		int ans;
		while (start <= end) {
			int mid = (start + end) / 2;
			int tempRest = 0; // 설치하는 휴게소 수
			ans = 0; // 구간의 최댓값
			for (int i = 0; i <= N; i++) {
				int install = (gap[i]-1)/mid;
				tempRest += install;
				if (install > 0) {
					ans = Math.max(ans, (gap[i]+install-1)/install);
				}
				else {
					ans = gap[i];
				}
			}
			if (tempRest > M) {
				start = mid + 1;
			} else {
				end = mid - 1;
			}
		}
		System.out.println(start);
	}
}