[BOJ] 1477 - 휴게소 세우기

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

BOJ - 휴게소 세우기

문제 유형: 이진 탐색, 매개변수 탐색(parametric search)

문제 난이도: Gold IV

시간 제한: 2초

메모리 제한: 128MB

 

문제

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

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

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

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

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

 

입력

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

 

출력

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

 

풀이

parametric search로 휴게소의 인터벌의 최대값을 최소로 맞춰보자.

lo = 1, hi = l로 하고, 배열을 정렬하고, 인터벌 최대길이 intervals를 mid로 한다.

배열을 순회하면서, 인터벌 최대길이를 intervals로 하면 기존 구간들 사이에 몇 개의 추가 설치가 필요한지 구한다.

 이제 순차적으로 배열을 순회하면서 구하면 되는데,

 이전 휴게소의 위치를 last로 두고, last + interval이 arr[i]보다 작은동안 남은횟수를 줄여가면서 last에 interval만큼 증가시킨다.

 그 이후, last를 arr[i]로 한다.

배열의 순호가 끝나도, 기존 휴게소 맨 마지막지점(배열의 끝요소)과 L까지의 인터벌도 똑같이 고려해야 한다.

여기서도 추가 설치가 필요하면 설치를 시도한다.

m번 초과로 설치가 필요하면 실패이고, 이하이면 성공이다.

성공 시, hi = mid-1로 길이를 더 줄이기 위해 다시 시도한다.

실패 시, lo = mid+1로 길이를 더 키우기 위해 다시 시도한다.

 

코드

Go

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

func check(interval, m, l int32, arr []int32) bool {
	last := int32(0)
	cnt := m
	for i := 0; i < len(arr); i++ {
		for last+interval < arr[i] {
			cnt--
			if cnt < 0 {
				return false
			}
			last += interval
		}
		last = arr[i]
	}

	for last+interval < l {
		cnt--
		if cnt < 0 {
			return false
		}
		last += interval
	}

	return true
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var n, m, l int32
	fmt.Fscan(reader, &n, &m, &l)

	arr := make([]int32, n)
	for i := int32(0); i < n; i++ {
		fmt.Fscan(reader, &arr[i])
	}

	sort.Slice(arr, func(i, j int) bool {
		return arr[i] < arr[j]
	})

	lo := int32(1)
	hi := l
	ans := int32(0)

	for lo <= hi {
		mid := (lo + hi) >> 1
		if check(mid, m, l, arr) {
			ans = mid
			hi = mid - 1
		} else {
			lo = mid + 1
		}
	}
	fmt.Fprintln(writer, ans)
}