BOJ 1477 - 휴게소 세우기
문제
기존 정점 n
(\(0 \le n \le 50\)), 추가하는 정점 m
(\(1 \le m \le 100\)), 선분의 길이 l
(\(100 \le l \le 1000\))이 주어질 때, 아래 조건에 맞춰 정점 간의 거리의 최댓값의 하한을 구해야 한다.
- \(n+m \lt l\)이다.
- 정점은
[1, l-1]
의 좌표에만 배치할 수 있다. - 이미 정점이 있는 좌표에는 배치할 수 없다.
- 좌표
0
과 첫 번째 정점 간의 거리, 마지막 정점과 좌표l
과의 거리 또한 거리의 최댓값을 구할 때 포함시킨다. - 정확히
m
개의 정점을 추가해야 한다.
풀이
- 정점 간의 거리를
curg
로 고정한다면, 거리의 최댓값은curg
이기 때문에,curg
를 최소화하는 문제로 바꿀 수 있다.- 거리가
curg
일 때m
개 이상의 정점이 필요하다면curg
를 늘려야 한다.
- 거리가
- 선분의 길이가
l
이기 때문에 가능한 거리는[1, l-1]
이다. 이 범위에서 이분 탐색을 진행하면 된다.- 이분 탐색을 해나가다보면 결국
curg
가 추가하는 정점이m
개인 거리로 수렴하게 되는데, 이 거리가 여러 개 있을 수가 있다.
이때 가장 작은curg
를 구해야 하기 때문에, 추가하는 정점이m
개일 때도 이분 탐색의 오른쪽 범위를 줄인다.
- 이분 탐색을 해나가다보면 결국
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, m, l, s = 0, e;
cin >> n >> m >> l;
vector<int> gaps, tt;
for (int i = 0; i < n; i++) {
int t;
cin >> t;
tt.push_back(t);
}
sort(tt.begin(), tt.end());
for (int i = 0; i < tt.size(); i++) {
gaps.push_back(tt[i] - s);
s = tt[i];
}
gaps.push_back(l - s);
s = 1;
e = l - 1;
while (s <= e) {
int curg = (s + e) / 2, curc = 0;
for (int i = 0; i < gaps.size(); i++) {
int r = gaps[i] % curg;
curc += gaps[i] / curg;
if (r == 0)
curc--;
}
if (curc <= m)
e = curg - 1;
else
s = curg + 1;
}
cout << s;
return 0;
}
풀고나서
- dp로 풀어보려 했지만, 상태 공간을 \(m \times l \times (n+m)\)으로 정의하고 시간복잡도를 계산했을 때 이 방법이 아닌 것을 알게 되었다.
- 휴게소 간의 거리를 기준으로 이분 탐색을 진행해야겠다는 생각을 바로 떠올리지 못했다.
- 탐색 범위와 비교 조건에 사용하는 변수의 관계가 비교적 복잡하기 때문에 Parametric search 태그도 추가된 것 같다.
Leave a comment