United Federation of Planets (UFP)는 1번부터 n번까지의 행성으로 구성된 선형 경로를 가진다. 각 행성은 고유의 우주선을 보유하며, 우주선마다 1광년을 이동하는 데 필요한 시간이 다르다.
행성 간 이동 시, 중간 행성에서 우주선을 갈아타는 것이 가능하지만, 탑승 준비 시간이 추가로 소요된다.
목표는 행성 1번에서 n번으로 이동할 때 걸리는 최소 시간을 계산하는 것이다.
5 5 10 4 8 3 6 8 3 4 8 15 4
107
이 문제는 DP(동적 계획법)와 Convex Hull Trick (CHT)을 결합해 해결한다.
int planetCount, prepTime[100001], speed[100001], cumulativeDistance[100001];
ll minTime[100001];
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];
}
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;
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]);
}
cout << minTime[planetCount] << '\n';
이 문제는 DP와 Convex Hull Trick (CHT)을 활용해 효율적으로 해결할 수 있었다.
문제 해결 과정에서 우주선을 효율적으로 갈아타는 방법을 고민하며, 선형 최적화 기법을 적용한 점이 인상 깊었다.
특히, DP와 CHT의 결합은 대규모 데이터 처리에서 뛰어난 성능을 보여줬다.