[1011] 백준 : Fly me to the Alpha Centauri(C++)

 

* 접근한 방법
- 각 수들의 규칙을 알아보려고 노력함
  사용자가 입력한 수들의 간격(d) = y - x

먼저 1부터 순차적으로 장치가 어떻게 이동하는지를 계산해보며,
장치 작동 횟수를 알아보았음

하다보니 수에 규칙성이 있는 것 같아서
장치 작동 횟수가 바뀌는 것만 따로 뽑아내서 적어 보았음(아래사진)

 

격줄마다 1(1제곱) -> 4(2제곱) -> 9(3제곱) -> 16 -> 25의 경계값이 있다는 것을 알 수 있었음
☞ d의 작동 횟수 경계값은 (i-1)의 제곱 < d <= i의 제곱임을 이용하고자 함
    이 범위 안에 있는 경우 작동 횟수 값은 = 2 * i - 1개

하지만, 이는 격줄마다 해당하는 것이므로 (i-1)^2 와 i^2의 사이의 또 다른 한줄의 규칙을 찾음
☞ d 작동횟수의 경계값(범위)은 i * (i-1) 이었음
    이 범위 안에 있는 경우 작동횟수 값은 = 2 * (i - 1)개

 

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
	int T = 0, x = 0, y = 0;
	cin >> T;

	for (int i = 0; i < T; i++)
	{
		cin >> x >> y;
		int d = y - x;
		for (int i = 1; ; i++)
		{
			if (d <= pow(i, 2) && d > pow(i - 1, 2))
			{
				if (d <= i * (i - 1))
					cout << 2 * (i - 1) << "\n";
				else
					cout << 2 * i - 1 << "\n";
				break;
			}
		}
	}

	return 0;
}