백준 Fly me to the Alpha Centauri(1011)

Fly me to the Alpha Centauri

1. 힌트

1) 공간 이동 장치 작동 횟수를 최소화하려면 최대한 속력을 높였다가 내려와야합니다.

2) 움직이는 과정을 수열로 나타내면 이와 같습니다.$1,\ 2,\ 3,\ x,\ ...,x,\ \ 3,\ 2,\ 1$

$2\displaystyle\sum_{k = 1}^{x}k=2\cfrac{x(x+1)}{2}=x(x+1)$

3) $1,\ 2,\ 3,\ x,\ ...,x,\ \ 3,\ 2,\ 1$

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;
		// dist를 넘지 않는 최대의 sum(lo)를 찾는다
		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(lg46341)$입니다

2) 테스트 케이스

jh05013님의 반례 모음