알고리즘 오답노트 10 (백준 - 1011)

Fly me to the Alpha Centauri

손으로 직접 수열을 적어가며 규칙을 찾는것이 포인트이다.

• 편의상 거리의 제곱근이 1.5보다 작으면 1.4로, 1.5보다 크면 1.6으로 적었다.

거리	거리의 제곱근	횟수
1	1	1
2	1.4	2
3	1.6	3
4	2	3
5	2.4	4
6	2.4	4
7	2.6	5
8	2.6	5
9	3	5
10	3.4	6
11	3.4	6
12	3.4	6
13	3.6	7
14	3.6	7
15	3.6	7
16	4	7
17	4.4	8
18	4.4	8
19	4.4	8
20	4.4	8
21	4.6	9

1. 거리의 제곱근이 정수면 횟수는 2n-1.
2. 거리의 제곱근의 소수부가 0.5보다 작으면 2 X (거리의 제곱근의 정수부)
3. 거리의 제곱근의 소수부가 0.5보다 크면 2 X (거리의 제곱근의 정수부) + 1

import math

num = int(input())
result = []
for i in range(num):
  start, finish = map(int, input().split())
  distance = finish - start
  
  sqrt_distance = math.sqrt(distance)
  if sqrt_distance - int(sqrt_distance) > 0.5:
    result.append(2 * int(sqrt_distance) + 1)
  elif sqrt_distance == int(sqrt_distance):
    result.append(2 * int(sqrt_distance) -1)
  else:
    result.append(2 * int(sqrt_distance))
    
for i in result:
  print(int(i))

• 문제 링크