1월 17일 - Star Trek[BOJ/17526]

Yullgiii·2025년 1월 16일
0

TIL: UFP 행성 간 최단 시간 이동 - Convex Hull Trick 활용

문제 설명

United Federation of Planets (UFP)는 1번부터 n번까지의 행성으로 구성된 선형 경로를 가진다. 각 행성은 고유의 우주선을 보유하며, 우주선마다 1광년을 이동하는 데 필요한 시간이 다르다.
행성 간 이동 시, 중간 행성에서 우주선을 갈아타는 것이 가능하지만, 탑승 준비 시간이 추가로 소요된다.

목표는 행성 1번에서 n번으로 이동할 때 걸리는 최소 시간을 계산하는 것이다.

이동 규칙

  • 인접한 행성 간의 거리는 입력으로 주어진다.
  • 각 행성의 우주선은 이동 속도(1광년당 시간)와 탑승 준비 시간이 존재한다.
  • 다른 행성으로 이동 시 우주선을 교체하면 준비 시간이 추가된다.

입력 조건

  1. 첫째 줄: 행성의 수 ( n ) (3 ≤ n ≤ 100,000)
  2. 둘째 줄: 인접한 행성 간 거리 ( n-1 )개
  3. 이후 ( n-1 )줄: 각 행성의 탑승 준비 시간우주선 속도

출력 조건

  • 행성 1번에서 n번까지 이동하는 데 필요한 최소 시간 출력

예제 입력 1

5 5 10 4 8 3 6 8 3 4 8 15 4

예제 출력 1

107


문제 해결 접근

이 문제는 DP(동적 계획법)Convex Hull Trick (CHT)을 결합해 해결한다.

  • DP로 최소 시간을 계산하되, 우주선을 갈아타는 비용을 효율적으로 계산해야 한다.
  • 우주선의 속도와 이동 거리를 직선의 기울기와 절편으로 변환해 선형 최적화 문제로 접근한다.

핵심 아이디어

  • 각 행성의 상태를 점으로 보고, 각 우주선의 속도준비 시간을 선형식으로 변환
  • Convex Hull Trick으로 최적의 경로를 빠르게 찾는다.

코드 설명

1. 데이터 구조 및 초기화

int planetCount, prepTime[100001], speed[100001], cumulativeDistance[100001];
ll minTime[100001];
  • planetCount: 행성의 수
  • prepTime: 각 행성의 우주선 준비 시간
  • speed: 각 행성의 우주선 속도
  • cumulativeDistance: 누적 거리 계산
  • minTime: i번째 행성까지의 최소 시간

2. 거리 및 우주선 정보 입력

for (int i = 2; i <= planetCount; i++) {
    cin >> cumulativeDistance[i];
    cumulativeDistance[i] += cumulativeDistance[i - 1];
}

for (int i = 1; i < planetCount; i++) {
    cin >> prepTime[i] >> speed[i];
}
  • 인접 행성 간 거리 입력 및 누적 거리 계산
  • 각 행성의 준비 시간과 속도 입력

3. Convex Hull Trick (CHT) 구조체

struct Line {
    mutable ll slope, intercept, point;
    bool operator<(const Line& other) const { return slope < other.slope; }
    bool operator<(ll x) const { return point < x; }
};

struct ConvexHullTrick : multiset<Line, less<>> {
    ll divide(ll numerator, ll denominator) {
        return numerator / denominator - ((numerator ^ denominator) < 0 && numerator % denominator);
    }

    bool isIntersecting(iterator x, iterator y) {
        if (y == end()) return x->point = LLONG_MAX, false;
        if (x->slope == y->slope) x->point = x->intercept > y->intercept ? LLONG_MAX : LLONG_MIN;
        else x->point = divide(y->intercept - x->intercept, x->slope - y->slope);
        return x->point >= y->point;
    }

    void insertLine(ll slope, ll intercept) {
        auto z = insert({slope, intercept, 0}), y = z++, x = y;
        while (isIntersecting(y, z)) z = erase(z);
        if (x != begin() && isIntersecting(--x, y)) isIntersecting(x, erase(y));
    }

    ll getMinimum(ll x) {
        auto l = *lower_bound(x);
        return l.slope * x + l.intercept;
    }
} CHT;
  • 직선의 기울기(slope)절편(intercept)을 이용해 최적화
  • Convex Hull Trick으로 최소 비용 경로를 효율적으로 탐색

4. DP 및 CHT 활용

CHT.insertLine(-speed[1], -prepTime[1]);

for (int i = 2; i <= planetCount; i++) {
    minTime[i] = -CHT.getMinimum(cumulativeDistance[i]);
    CHT.insertLine(-speed[i], (ll)speed[i] * cumulativeDistance[i] - minTime[i] - prepTime[i]);
}
  • 첫 번째 행성의 우주선을 기반으로 시작
  • i번째 행성까지의 최소 시간을 계산하고, 해당 우주선을 CHT에 추가

5. 최종 결과 출력

cout << minTime[planetCount] << '\n';
  • 최종 목적지인 n번째 행성까지 도달하는 최소 시간 출력

So...

이 문제는 DP와 Convex Hull Trick (CHT)을 활용해 효율적으로 해결할 수 있었다.

  • 우주선의 속도와 준비 시간을 선형식으로 변환하여 최적화
  • CHT를 통해 빠르게 최적의 경로를 찾음

문제 해결 과정에서 우주선을 효율적으로 갈아타는 방법을 고민하며, 선형 최적화 기법을 적용한 점이 인상 깊었다.
특히, DP와 CHT의 결합은 대규모 데이터 처리에서 뛰어난 성능을 보여줬다.

profile
개발이란 무엇인가..를 공부하는 거북이의 성장일기 🐢

0개의 댓글