[백준] Fly me to the Alpha Centauri

https://www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri

 

오랜만에 올립니다.

 

k 광년을 이동했을 때 다음에는 k-1, k, k+1 광년을 이동할 수 있다는 조건과 마지막은 1광년을 남겨야 하는 조건 때문에 최소한의 공간이동은 대칭적인 성격을 가질 수밖에 없다.

 

1 (1 * 1)

 

1 1 (2 * 1)

 

1 2 1 (2 * 2)

 

1 2 2 1 (3 * 2)

 

1 2 3 2 1 (3 * 3)

 

1 2 3 3 2 1 (4 * 3)

 

1 2 3 4 3 2 1 (4 * 4)

 

위와 같은 규칙을 가지며 마지막 행을 예로 들면 16은 최소한 7번을 이동을 할 수 있는 수 중에서 가장 큰 수다.

또한, 12는 최소한 6번을 이동할 수 있는 수 중 가장 큰 수로 12보다 크고 16보다 작거나 같으면 최소한 7번을 이동할 수 있다.

 

새해 복 많이 받으세요.

 

import sys

T = int(sys.stdin.readline())

for i in range(T):    
    x, y = map(int, sys.stdin.readline().split())
    z = y - x
    d1, d2 = 1, 1
    n = 1
    
    while z > d1 * d2:
        if n % 2 == 1:
            d1 += 1
        else:
            d2 += 1

        n += 1

    print(n)