[백준] 1011번 Fly me to the Alpha Centauri ★★

💡문제접근

• 되게 간단한 문제라고 생각했는데 규칙을 파악하고 이를 코드로 옮기는 과정에서 많은 시간이 걸렸다.
• 장치의 가동 횟수가 최소가 되게끔 하도록 이동한다면 아래와 같은 규칙이 나오게 되고 거리의 제곱근을 기준으로 계산하면 문제를 해결할 수 있다.
• 1 + 2 + ... + (n-1) + n + (n-1) + ... + 2 + 1 = n^2이 된다.

💡코드(메모리 : 31256KB, 시간 : 332ms)

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    x, y = map(int, input().strip().split())
    distance = y - x
    gap = 1
    while True:
        if distance <= gap * (gap + 1):
            break
        gap += 1

    if distance <= (gap ** 2):
        print(2 * gap - 1)
    else:
        print(2 * gap)

💡소요시간 : 47m