[백준] Fly me to the Alpha Centauri

문제_

https://www.acmicpc.net/problem/1011
골드V

풀이_

N광년일 때 이동 경로를 그리고, 이동 회수를 표로 그리면 다음과 같다.

광년	이동 경로	이동 횟수
2	11	2	o
3	121	3	o
4	121	3	|
5	1211	4	o
6	1221	4	|
7	12211	5	o
8	12221	5	|
9	12321	5	|
10	123211	6	o
11	123221	6	|
12	123321	6	|
13	1233211	7	o
14	1233221	7	|
15	1233321	7	|
16	1234321	7	|
17	12343211	8	o

3 이후의 늘어난 구간을 살펴보면 5 7 10 13 17이 있다. 이 수들의 이전 숫자는 4 6 9 12 16.
잘 보면 4 9 16은 제곱수임을 알 수 있고, 6 12는 제곱수 사이의 중간값을 버림한 값이라는 것을 알 수 있다.

거리가 N^2일 때의 이동 횟수는 몇 개일까?
4일 때 3, 9일 때 5, 16일 때 7인데, 이를 잘 보면 홀수(2n - 1)의 형태이고 여기서 n은 제곱수의 제곱근이다.
즉 거리가 N^2일 때의 이동 횟수는 2 x sqrt(n) - 1이다.

그럼 거리가 N^2보다 작을 경우(제곱근이 아닌 경우)의 이동 횟수는 (N-1)^2 -1 ~ N^2 - 1가 되는데,
위에서 제곱수 사이의 중간값을 버림한 값을 넘으면 개수가 1개 추가되는 것을 알 수 있다.
즉 이동 횟수의 값의 범위는 최소~중간이 같은 값이고, 중간+1~최대가 같은 값(이전값+1)임을 알 수 있다.

이를 코드로 옮기면 다음과 같다.

from math import ceil, floor, sqrt

def solution(x, y):
  distance = y - x
  sqrt_distance = sqrt(distance)

  # 거리가 n^2 이하인 수가 가질 수 있는 최대의 최소이동횟수 = 2*n - 1
  max_count = (2 * ceil(sqrt_distance)) - 1

  up = ceil(sqrt_distance) ** 2
  down = floor(sqrt_distance) ** 2
  mid = (up + down) // 2

  if up == down or distance > mid:
    return max_count
  else:
    return max_count - 1

num_of_inputs = int(input())
inputs = [map(int, input().split()) for _ in range(num_of_inputs)]

for x, y in inputs:
  print(solution(x,y))

예를 들어, 15의 경우 9~16사이의 수이다(up, down). 그리고 중간값(mid)은 12.
16의 최소이동횟수는 7개. 15는 중간값 12보다 크므로 최소이동횟수는 16과 같은 7개이다.