[백준 알고리즘: python 3] #1011 - Fly me to the Alpha Centauri

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

 

1011번은 알파 센타우리라는 행성으로 날아가고자 하는 한 우주선이 문제의 규칙에 따라 공간이동장치로 날아갈 때 공간 이동 장치의 촤소한의 작동횟수를 구하는 문제입니다. 이 문제도 거리가 1일 때부터 하나씩 손으로 풀며 규칙을 찾아 풀었습니다.

 

거리	이동 방식	최소 횟수
1	1	1
2	1, 1	2
3	1, 1, 1	3
4	1, 2, 1	3
5	1, 2, 1, 1	4
6	1, 2, 2, 1	4
7	1, 1, 2, 2, 1	5
8	1, 2, 2, 2, 1	5
9	1, 2, 3, 2, 1	5
10	1, 1, 2, 3, 2, 1	6
11	1, 2, 2, 3, 2, 1	6
12	1, 2, 3, 3, 2, 1	6
13	1, 1, 2, 3, 3, 2, 1	7
14	1, 2, 2, 3, 3, 2, 1	7
15	1, 2, 3, 3, 3, 2, 1	7
16	1, 2, 3, 4, 3, 2, 1	7

 

최소 횟수의 규칙을 보면 제곱수가 나오는 시점에 홀수(2*제곱수 - 1)의 최소 횟수가 끝이되고 다시 그 다음 짝수의 최소횟수가 반복됩니다. 그리고 서로 인접한 제곱수의 딱 절반을 기준으로 짝수와 홀수가 나뉘고 있지요! (9와 16 사이를 보세요. 그리고 9 + 16의 절반은 12.5이고 이를 기준으로 값이 나뉘고 있습니다.)

 

그렇다면,

1. 출발지와 도착지 사이의 거리를 구한 뒤, 그 수의 제곱근을 구하고 올림합니다. 이 수를 factor라고 정의합니다. (예를 들면, 14의 제곱근은 3.XXX인데 이 때 올림하여 factor = 4 입니다.)
2. factor - 1의 제곱을 flag1(= 9), factor의 제곱을 flag2(= 16) 라고 정의합니다.
3. 그리고 (flag1 + flag2) / 2 (= 12.5) 를 기준으로 이보다 크다면 factor * 2 - 1을, 그렇지 않다면 factor * 2 - 2를 최소 횟수로 정합니다.

코드는 다음과 같습니다.

 

import sys
import math

T = int(sys.stdin.readline())
results = []

for _ in range(T):
    x, y = map(int, sys.stdin.readline().split())
    distance = y - x

    factor = math.ceil(math.sqrt(distance))

    flag1 = (factor - 1) ** 2
    flag2 = factor ** 2

    if distance >= (flag1 + flag2) / 2: res = factor * 2 - 1
    else: res = factor * 2 - 2

    results.append(res)

for result in results:
    sys.stdout.write(str(result)+'\n')