https://www.acmicpc.net/problem/1011
시간 2초, 메모리 512MB

input :

• 테스트케이스의 개수 T
• x y (현재 위치, 목표 위치)

output :

• x지점으로부터 y지점까지 정확히 도달하는데 필요한 최소한의 공간이동 장치 작동 횟수를 출력

조건 :

• 이전 작동시기에 k광년을 이동하였을 때는 k-1 , k 혹은 k+1 광년만을 다시 이동

• 처음 작동시킬 경우 -1 , 0 , 1 광년을 이론상 이동 그러나, 의미가 없으므로 1 광년을 이동

---

과거에 풀었던 문제로 친구랑 전화하다 이 문제 풀고 있다 그래서 다시 봤다. 글을 써놓지 않아서 다시 어떻게 사고했는지를 생각하며 복기했다.

생각해야할 것.

1. 거리의 차이로 최소 작동 횟수 정해지나?
2. 최소 작동 횟수는 어떤 규칙이 있는가?

-> 1.에 대해서는 그러하고 2.에 대해서는 표를 작성하는 것이 편리하다.
-> 매번 그려보자, 써보자 하면서 이건 습관을 들이지 못했다. 고쳐 나가자.

규칙

거리 차이 가 3이 날 때 부터 규칙을 찾아야 한다. 그리고 생각한 부분은 "5", "7", "10" 부분과 같이 [1 ... 1 1]처럼 1을 3개 가지고 있는 부분들을 분기점으로 생각하는 것이다.

시작과 끝에서는 언제나 1씩 이동하기 때문에 대칭을 이룬다고 볼 수 있다. 그러나 대칭이 깨지는 부분? 암튼 이 부분이 좀 특이해서 여기를 골랐다.

시작 할 떄는 거리차이를 3, [1 1 1]이 있다고 가정을 하고 시작하는 것이다.

그리고 2를 추가해서 [1 2 1 1]의 형태를 만들어 거리차이를 메꿀 수 있는지 확인한다.
이 거리차이보다 실제로 작다면 문제가 요구하는 정답은 해당 횟수 - 1을 하면 얻을 수 있다.

실제로 거리차이가 5보다 크면 [1 2 2 1 1]보다 작은지 확인하고, 그 다음에는 3을 추가한다.
[1 2 3 2 1 1]을 확인하고.... 계속 하는 것

다르게 확인할 수도 있기 때문에 다른 방식을 아는 것도 좋을 것 같다.

import sys

for _ in range(int(sys.stdin.readline())):
    x, y = map(int, sys.stdin.readline().split())

    if y - x <= 2:
        print(y - x)
        continue

    diff, ans = 3, 3
    temp, cnt = 2, 0
    while diff <= y - x:
        if cnt == 2:
            cnt = 0
            temp += 1

        diff += temp
        ans += 1
        cnt += 1

    print(ans - 1)