1011. Fly me to the Alpha Centauri

T = int(input())

for _ in range(T):
    x, y = map(int,input().split())
    d = y-x
    n = 0

    while d > n**2:
        n += 1

    if (n**2)-d < n:
        print(2*n-1)
    else:
        print(2*n-2)

 

• 이 문제는 이동해야하는 총 거리에 따라 이동횟수를 구하는 문제입니다. 문제에 따르면 거리에 따른 이동은 다음과 같이 이루어집니다.
  

  

• 저는 여기서 $d=n^2$이 되는 지점에 주목했습니다. ex: ( 1 ),  (1 2 1),  ( 1 2 3 2 1),  ( 1 2 3 4 3 2 1 )
  1. $ (n-1)^2 \lt d \le n^2 $ 을 만족하는 $n$을 찾습니다.
  2. 위의 예시에서 알 수 있듯이 n을 찾게되면 이동횟수는 $2n-2$ 또는 $2n-1$ 중 하나가 됩니다.
  3. 1번방식대로 계산하면 $(n-1)^2$와 $n^2$ 사이에 있을 수 있는 값은 $2n-1$개 입니다.
  4. $2n-1$개의 $d$ 중에서 $n^2$과 가까운 $n$개는 이동횟수가 $2n-1$, 나머지 $n-1$개는 이동횟수가 $2n-2$입니다.
  5. 이를 이용해 최종 이동횟수를 결정해줍니다.
  
  
• 예시 ( d = 7 )
  1. $ 4 \lt d \le 9 $ 이므로 $n=3$
  2. 최종 출력값인 이동횟수는 4 또는 5
  3. 4 또는 5의 이동횟수를 갖는 d는 총 5개 ( 5, 6, 7, 8, 9 )
  4. 5개 중 9와 가까운 3개 ( 7, 8, 9 )는 이동횟수가 5, 나머지는 4
  5. 최종 정답은 5