Fly me to the Alpha Centauri
1. 힌트
1) 공간 이동 장치 작동 횟수를 최소화하려면 최대한 속력을 높였다가 내려와야합니다.
2) 움직이는 과정을 수열로 나타내면 이와 같습니다.1, 2, 3, x, ...,x, 3, 2, 1 이와 같은 수열을 양 끝부터 최대한 채운다고 생각하면 어디까지 속력을 올렸다가 내려올 수 있는지 계산할 수 있습니다. 만약 최고 속력을 x까지 올렸다가 내려오는 방식으로 이동할 때, 이동하는 거리는 이와 같습니다.
2×k=1∑xk=2×2x(x+1)=x(x+1)
3) 1, 2, 3, x, ...,x, 3, 2, 1 물론, 이렇게 최대한 채웠는데 가운데 거리가 남을 수도 있습니다. 가운데 남은 거리가 x−1, x, x+1이면 한 번만 더 공간 이동 장치를 작동시키면 되지만, 그 외에 다른 경우는 어떻게 해결할까요? 그 방법은 작동 순서를 바꾸는 것입니다. 예를 들어 1, 2, 3, (1), 3, 2, 1 가운데 1이 남았다면 이를 왼쪽 혹은 오른쪽에 위치하는 1의 위치로 옮깁니다. 이런 식으로 남은 수는 반드시 x보다 같거나 작으므로 처리할 수 있습니다.
2. 접근
힌트 참조
3. 구현
최대한 올라갈 수 있는 속도를 구할 때, 이분 탐색을 사용했습니다. 사실 그냥 O(N)으로 순차 탐색해도 올라갈 수 있는 속력은 46341이 최대이기때문에 시간 안에 돌아갑니다.
#include <stdio.h>
int main() {
int T, x, y;
scanf("%d", &T);
while (T--) {
scanf("%d %d", &x, &y);
int dist = y - x;
long long lo = 0; long long hi = 46341;
while (lo + 1 < hi) {
long long mid = (lo + hi) / 2;
if (mid * (mid + 1) > dist) hi = mid;
else lo = mid;
}
int cnt = 2 * lo;
dist -= lo * (lo + 1);
if (dist == 0);
else if (dist <= lo + 1) cnt++;
else cnt += 2;
printf("%d\n", cnt);
}
}
1) 시간 복잡도
이분 탐색을 사용하므로 O(log46341)입니다
2) 테스트 케이스
jh05013님의 반례 모음