백준 1011번: Fly me to the Alpha Centauri
수학 문제다. 1 121 12321 1234321 각각 1, 4, 9, 16… 모두 제곱수다. 제곱수를 기준으로 대칭이 된다. 9는 5칸, 10, 11, 12는 12321에 1, 2, 3을 하나씩 추가하면 되니까 6칸, 13, 14, 15는 123321에 1, 2, 3을 하나씩 추가하면 되니까 7칸이다. 제곱수 사이에 있는 짝수 개의 수을 절반으로 나누면 각각 같은 칸을 움직인다.
import sys
import math
input = sys.stdin.readline
def solve(n):
v = math.sqrt(n)
s = math.floor(v)
e = s + 1
ans = 2 * s - 1
if n == s ** 2:
pass
elif n - s**2 <= (e**2 - s**2) // 2:
ans += 1
else:
ans += 2
print(ans)
T = int(input())
for _ in range(T):
x, y = map(int, input().split())
dist = y - x
solve(dist)
대학교 1학년때 풀다 어려워서 도망간 문제다. 이걸 왜 못풀었지?