[math2/Python] 1011번: Fly me to the Alpha Centaur - 효과는 굉장했다!

1011번: Fly me to the Alpha Centauri

 

알고리즘 분류

• 수학

 

 

SOLUTION

import sys
from math import sqrt

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

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

    distance = y - x
    diff = int(sqrt(distance))

    # distance가 1,2,3 일 때 규칙에서 예외이므로 그대로 distance값 출력
    if distance < 4:
        cnt = distance
   
    # distance 가 distance의 제곱 + distance의 제곱근 일 때
    elif distance > diff**2 + diff:
        cnt = diff*2 + 1 

    elif diff**2 < distance <= diff**2 + diff:
        cnt = diff*2

    elif distance == diff**2:
        cnt = diff*2 - 1

    print(cnt)
    
'''
규칙 : 제곱근을 한계로 제곱 + 제곱근 형태 이후로 cnt += 1

1   1                   cnt = 1
2   11                  cnt = 2     1,2,3 일때는 예외 distance 값 그대로 cnt 에 할당됨
3   111                 cnt = 3     
4   121     (2^2)       cnt = 3   
5   1211                cnt = 4     
6   1221    (2^2 + 2)   cnt = 4     
7   12211               cnt = 5
8   12221               cnt = 5
9   12321   (3^2)       cnt = 5
10  123211              cnt = 6     
11  123221              cnt = 6 
12  123321              cnt = 6
13  1233211 (3^2 + 3)   cnt = 6
14                      cnt = 7 
'''