백준 Fly me to the Alpha Centauri(1011)

axiom·2021년 6월 27일

Fly me to the Alpha Centauri

1. 힌트

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

2) 움직이는 과정을 수열로 나타내면 이와 같습니다. $1,\ 2,\ 3,\ x,\ ...,x,\ \ 3,\ 2,\ 1$ 이와 같은 수열을 양 끝부터 최대한 채운다고 생각하면 어디까지 속력을 올렸다가 내려올 수 있는지 계산할 수 있습니다. 만약 최고 속력을 $x$ 까지 올렸다가 내려오는 방식으로 이동할 때, 이동하는 거리는 이와 같습니다.

$2\times \displaystyle\sum_{k = 1}^{x}k=2\times\cfrac{x(x+1)}{2}=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. 구현

최대한 올라갈 수 있는 속도를 구할 때, 이분 탐색을 사용했습니다. 사실 그냥 $\mathcal{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);
	}
}