백준 1011 Fly me to the Alpha Centauri / python

문제 :

풀이 point

거리와 이동횟수의 상관관계를 파악하는 것이 중요하다.

거리가 1 ~ 10까지 증가할 때 거리, 이동횟수, 이동방법이 어떻게 변화하는지 파악해야한다.

풀이 방법

d(거리)   이동(예시)         최소 횟수
1   		1                 1
2   		1+1               2
3   		1+1+1             3
4   		1+2+1             3
5   		1+2+1+1           4
6   		1+2+2+1           4
7   		1+2+2+1+1         5
8   		1+2+2+2+1         5
9   		1+2+3+2+1         5
10  		1+2+3+2+1+1       6
11  		1+2+3+2+2+1       6
12  		1+2+3+3+2+1       6
13  		1+2+3+3+2+1+1     7

여기서 d(거리)가 제곱수 구간 ex) 4 < x < 9 일때 기준에 따라 최소 이동 횟수가 변경되는 것을 알 수 있다.

n = 루트(거리)의 정수부 ex) 5 -> 2

만약 거리 n^2 = 이동 횟수 : 2n-1
거리 <= n^2+n = 이동 횟수 : 2n
거리 > n^2+n = 이동 횟수 : 2n+1

그 이유는 이동방법이 대칭이기 때문이다

1. 거리가 제곱수일 때 이동 방법은 ex) 9 : 1+2+3+2+1
2. 제곱수 이상인데 최고 숫자를 두번 쓰는 경우 : 1+2+3+3+2+1 -> 10~12까지는 제곱수보다 이동 횟수가 +1
3. 최고 숫자가 이전 최고 숫자보다 +1 될 경우 ex) 1+2+3+4+3+2+1 이동 횟수가 2번째 경우보다 +1

풀이 코드

import math

for _ in range(int(input())):
  x, y = map(int, input().split())
  dist = y-x

  n = math.isqrt(dist)

  if dist == n*n:
    print(2*n-1)
  elif dist <= n*n+n:
    print(2*n)
  else:
    print(2*n+1)