백준 1011

백준 1011번 "Fly me to the Alpha Centauri" 문제는 행성 간 이동 거리를 최소화하는 방법을 찾는 문제입니다.
우주선은 출발지점에서 시작해서 Alpha Centauri까지 이동해야 합니다. 그리고 각 이동 단계에서, 우주선은 다음과 같이 이동할 수 있습니다.
이전 이동 거리보다 1이 증가된 거리를 이동 (즉, 1, 2, 3, 4, ... )
이전 이동 거리보다 1이 감소된 거리를 이동 (즉, ..., 4, 3, 2, 1)
예를 들어, 시작지점에서 Alpha Centauri까지 거리가 5라면, 우주선은 다음과 같이 이동할 수 있습니다.

1 -> 2 -> 3 -> 2 -> 1
1 -> 2 -> 1 -> 2 -> 3 -> 2 -> 1
이 문제에서는 이동 횟수가 가장 적게 이루어지는 방법을 찾아야 합니다. 따라서, 최소 이동 횟수를 찾기 위해 다양한 방법이 존재합니다.
현재 위치와 목표 위치의 차이를 구하여 이동 거리의 최솟값과 최댓값을 구한 후, 최솟값 + 최댓값을 구합니다.
목표 지점에 도달할 때까지 이동하는 데 필요한 이동 거리를 계산합니다.
이전 이동 거리와 현재 이동 거리 간의 차이를 이용하여 문제를 해결합니다.

이 중에서 1번 방법은 현재 위치와 목표 위치의 차이에 따라서 계산해야 할 값이 계속해서 변동하므로, 코드 작성이 복잡해지는 단점이 있습니다. 반면에 2번 방법은 이동 거리를 계산할 때 무한대를 고려해야 하기 때문에 코드 작성이 까다로운 단점이 있습니다.
따라서, 대부분의 사람들은 3번 방법을 이용하여 문제를 해결합니다. 3번 방법에서는 이전 이동 거리와 현재 이동 거리 간의 차이를 구하는 식을 이용합니다.

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    int t;
    cin >> t;
    while (t--) {
        int x, y;
        cin >> x >> y;
        int dist = y - x; // 거리 계산
        int n = sqrt(dist);
        int answer = n * 2 - 1; // 최소 이동 횟수 초기값 설정
        if (dist > n * n) {
            answer += 1;
        }
        if (dist > n * n + n) {
            answer += 1;
        }
        cout << answer << '\n';
    }
    return 0;
}