문제

기존 정점 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