[C++] 백준 10111번 Fly me to the Alpha Centauri

수학 문제입니다.

x행성에서 y행성까지 이동할때 최소 워프 횟수를 구하는 문제입니다.
워프는 처음에 이동 거리는 1이며
그다음은 이동거리 -1, 0, +1로 이동이 가능합니다.

예를들어 현재 이동거리가 5이면 다음에는 4, 5, 6 중 하나의 이동을 할 수 있습니다.
마지막에 도착지는 이동을 1만큼 해야합니다.

이동거리에 따른 최대 거리는 다음과 같습니다.
1 = 1                      = 1 * 1
2 = 1 1
3 = 1 2 1                 = 2 * 2
4 = 1 2 2 1
5 = 1 2 3 2 1            = 3 * 3
6 = 1 2 3 3 2 1
7 = 1 2 3 4 3 2 1       = 4 * 4
8 = 1 2 3 4 4 3 2 1
9 = 1 2 3 4 5 4 3 2 1  = 5 * 5

1, 3, 5 ,7 ,9. 즉 홀수의 숫자를 보면 최대이동 거리가
제곱의 형태를 가지는 것을 알 수 있습니다.

이를 통해 1의 제곱, 2의 제곱, 3의 제곱 ..... n의 제곱을 해나가면서
가야하는 거리랑 비교를 하며 제곱의 수가 거리보다 커졌을 때

n * 2 - 1인지
n * 2 - 2인지 확인해야합니다.

이를 위해 n * n 에 n을 빼서 거리보다 큰지 작은지 비교해서 알 수 있습니다.

 

#include <iostream>
using namespace std;

int main(int argc, char *argv[])
{
	int testcase;
	scanf("%d", &testcase);

	while (testcase--)
	{
		int x, y;
		long long i = 0;

		scanf("%d", &x);
		scanf("%d", &y);

		long long dist = y - x;

		while (++i) {
			i;
			if (dist <= i * i) {
				break;
			}
		}
        if (dist <= i * i - i) {
            printf("%d\n", i * 2 - 2);
        }
        else {
            printf("%d\n", i * 2 - 1);
        }
	}
	return 0;
}