[백준 1011번 ] Fly me to the Alpha Centauri (파이썬/python)

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

1011번: Fly me to the Alpha Centauri

 

생각보다 시간 많이 잡아먹은 문제.... 규칙을 알아야 풀 수 있는 문제였다

 

이 표를 보면 거리, 경로, 이동횟수, 이동횟수가 반복되는 횟수가 나온다

반복되는 횟수는 1 1 2 2 3 3 4 4 이렇게.

이거에 따라 이동횟수가 반복된다.

 

저 규칙을 보고 제곱의 성질을 이용해서 문제풀었다. 더 깔끔한 풀이가 있겠지만 이게 한계다..

 

 

import sys
from math import sqrt
 
input = sys.stdin.readline
 
t = int(input())
for _ in range(t):
 
    x, y = map(int, input().strip().split())
    distance = y - x
 
    sqrt_distance = int(sqrt(distance))
 
    if sqrt_distance * sqrt_distance == distance:
        cnt = sqrt_distance * 2 - 1
 
    elif distance > (sqrt_distance * sqrt_distance) and distance <= ((sqrt_distance * sqrt_distance) + sqrt_distance):
        cnt = sqrt_distance * 2
 
 
    elif distance > ((sqrt_distance * sqrt_distance) + sqrt_distance):
        cnt = sqrt_distance * 2 + 1
 
    if distance <= 3:
        cnt = distance
 
    print(cnt)