오늘 풀어본 두번째 문제는 BOJ 1477 휴게소 세우기 이다.
BOJ 1477 휴게소 세우기
다솜이는 유료 고속도로를 가지고 있다. 다솜이는 현재 고속도로에 휴게소를 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개의 휴게소를 짓고 난 후에 휴게소가 없는 구간의 최댓값의 최솟값을 출력한다.
풀이
이분 탐색에서 역시나 가장 중요한 것은 이분탐색의 기준을 무엇으로 잡느냐 이다.
여러 블로그에서 그랬듯이 나 역시 처음엔 가장 큰 구간을 기준으로 절반씩 쪼개서 하나씩 설치해야 하나,,? 그럼 우선순위 큐를 사용하면 될 것 같은데,, 하는 생각을 했었다.
하지만 그럴 경우,
만약 {0,300,500} 과 같이 설치된 도로에 3개의 휴게소를 설치할 경우 차례대로 150, 400, 75 지점에 휴게소가 세워지게 되어 150이 결과 값으로 도출되지만
사실 100,200,400 지점에 3개의 새로운 휴게소를 설치한다면 정답은 100이 되는 반례가 존재한다.
즉, 이분 탐색의 기준이 단순히 거리는 아닌 것이다.
고민하다가 결국 블로그를 찾아보았고 탐색의 기준은 "휴게소 M개 사이의 거리를 distance 로 하였을 때 몇개의 휴게소를 새로 세울 수 있느냐" 였다.
휴게소를 전체 구간 중 정 가운데에 세울 때부터 시작해 구간의 중간 값을 간격으로 두고, 해당 간격을 유지하며 휴게소를 세웠을 때 세울 수 있는 휴게소를 count 한다.
count 값이 M 보다 크다면 간격을 넓혀야 하므로 left=mid+1, 그 반대라면 간격을 줄여야 하므로 right=mid-1 을 통해 적절한 간격을 찾아나간다.
이때 우리는 최소의 간격을 찾아야 하는 것이므로 count 값이 M 과 같은 경우엔 한번 더 줄여볼 수 있도록 right를 조절하는 쪽에 포함되도록 하여야 했고 right 를 마지막으로 조절하기 때문에 정답을 left 값으로 반환하는것이 좀 이해가 잘 되지 않았다.
여러모로 아직 이분탐색 연습이 필요한 것 같다..!
코드
cpp
#include <iostream>
#include <vector>
#include <algorithm>
// boj 1477 휴게소 세우기, 골드 4, 이분 탐색
using namespace std;
int binary_search(vector<int> store_position, int M, int L){
int left = 1, right = L-1;
while (left<=right){
int mid = (left+right)/2;
int count = 0;
for (int i = 1; i < store_position.size(); ++i) {
int section = store_position[i]-store_position[i-1];
count += section/mid;
if(section%mid == 0) count--;
}
if(count>M) left = mid+1;
else right = mid-1;
}
return left;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int N, M, L;
cin>>N>>M>>L;
vector<int> store_position(N+2);
store_position[0] = 0;
for (int i = 1; i <= N; ++i) cin>>store_position[i];
store_position[N+1] = L;
sort(store_position.begin(), store_position.end());
cout<<binary_search(store_position, M, L);
return 0;
}swift
// boj 1477 휴게소 세우기, 이분탐색, 골드 4
import Foundation
func binary_search(_ position : [Int], _ N : Int, _ M : Int, _ L : Int) -> Int{
let store_position = position.sorted(by: { $0 < $1})
var left = 1
var right = L-1
var mid = -1
var answer = 0
while(left<=right){
mid = (left+right) / 2
var count = 0
for i in 1...store_position.count-1 {
let distance = store_position[i]-store_position[i-1]
count += distance/mid
if(distance%mid == 0){
count -= 1
}
}
if count>M {
left = mid+1
}else{
right = mid-1
}
}
return left
}
var line = readLine()
var N = -1
var M = -1
var L = -1
if let input = line {
var array = input.components(separatedBy: " ")
N = Int(array[0])!
M = Int(array[1])!
L = Int(array[2])!
}
var position = readLine()
var store_positions = [0, L]
if let pos = position {
var array = pos.components(separatedBy: " ")
for store in array {
store_positions.append(Int(store)!)
}
}
print(binary_search(store_positions, N, M, L))
Reference
