백준] 1011- Fly me to the Alpha Centauri

시간 제한 : 2초

메모리 제한 : 128MB

입력

입력의 첫 줄에는 테스트케이스의 개수 T가 주어진다. 각각의 테스트 케이스에 대해 현재 위치 x 와 목표 위치 y 가 정수로 주어지며, x는 항상 y보다 작은 값을 갖는다. ( 0 ≤ x < y < 2^31)

출력

각 테스트 케이스에 대해 x지점으로부터 y지점까지 정확히 도달하는데 필요한 최소한의 공간이동 장치 작동 회수를 출력한다.

소스코드

#include <iostream>
#include <math.h>
using namespace std;
int main(void)
{
	long long dist, w, dist2;
	int s, e, t;
	cin >> t;
	while (t--)
	{
		cin >> s >> e;
		dist = e - s;
		for (w = 1; w*w <= dist; w++);
		w--;

		dist2 = dist - w*w;
	        dist2 = (long long)ceil((double)dist2 / w);
		cout << w * 2 - 1 + dist2 << '\n';
	}
}

Tip

백준에서는 이를 규칙 찾기로만 분류했지만 수학적으로도 풀 수 있다. 규칙 찾기는 아무래도 n번 움직일 때 최대로 이동할 수 있는 거리를 구하는 정도?