문제

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

---

접근

x부터 y 까지의 이동횟수를 구하는 문제로, 사실 상 x, y의 값 자체에 대한 의미 보다는 y-x 값을 이용하여 문제 속 규칙을 발견할 수 있다.

y-x(거리)	이동횟수(return 값)	이동방법
1 (1의 제곱)	1	1
2	2	1 1
3	3	1 1 1
4 (2의 제곱)	3	1 2 1
5	4	1 2 1 1
6	4	1 2 2 1
7	5	1 2 2 1 1
8	5	1 2 2 2 1
9 (3의 제곱)	5	1 2 3 2 1
10	6	1 2 3 2 1 1
11	6	1 2 3 2 2 1
12	6	1 2 3 3 2 1
13	7	1 2 3 3 2 1 1
14	7	1 2 3 3 2 2 1
15	7	1 2 3 3 3 2 1
16 (4의 제곱)	7	1 2 3 4 3 2 1
17	8	1 2 3 4 3 2 1 1
..	..	..

이동횟수는 [1], [2], [3, 3], [4, 4], [5, 5, 5], [6, 6, 6], [7, 7, 7, 7], [8, 8, 8, 8] ...
로 증가한다.

이 때, i의 제곱 값을 이용하면 반복문을 사용하지 않고 풀 수 있다.

i	y-x(i의 제곱)	이동횟수(return 값)	i+(i-1) = 2*i - 1
1	1	1	1+0 = 2*1 - 1
2	4	3	2+1 = 2*2 - 1
3	9	5	3+2 = 2*3 - 1
4	16	7	4+3 = 2*4 - 1
5	25	9	5+4 = 2*5 - 1
..	..	..	..

---

코드

📌 python

import sys, math
input = sys.stdin.readline

case = int(input())

for _ in range(case) :
    x, y = map(int, input().split())
    distance = y-x
    i = math.ceil( distance**0.5 )

    if(i**2 - (i-1) > distance) : 
        print(2*i-2)
    else :
        print(2*i-1)