[Python3] BOJ - 1011 "Fly me to the Alpha Centauri"

 # 문제 링크 : https://www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri

 # 풀이 :

 개인적으로 문제의 핵심은 가장 마지막의 이동거리는 1광년이라는 것이다. 따라서 공간이동의 패턴은 항상 어떤 최고점을 찍고 내려오는 형상을 띈다는 것이다. 

차이 ( y - x )	이동
4	1 - 2 - 1
5	1 - 2 - 1 - 1
6	1 - 2 - 2 - 1
?	1 - 2 - 3 - 2 - 1

 이 때 5는 4의 이동 거리에서 1만 더 가면 되므로 1 - 2 - 1 - 1이 된다. 1 - 2 - 2는 문제의 조건(붉은 글씨)에 위배 되기 때문에 성립할 수 없다. 그렇다면 6은 1 - 2 - 1 - 1 - 1이라고 생각할 수 있다. 이 경우 문제의 조건에는 위배되지 않지만, 마지막 1을 제외하고 두개의 1은 2로 합칠 수 있다. 따라서 6은 1 - 2 - 2 - 1의 패턴을 가진다.

 이러한 패턴 중 (1 - 2 - 1), (1 - 2 - 3 - 2 - 1), (1 - 2 - 3 - 4 - 3 - 2 - 1)... 처럼 계속 증가하다가 계속 감소하는 모습을 볼 수 있다. 이 패턴을 모두 합하면 항상 중간에 위치한 값(2, 3, 4)의 제곱이 됨을 알 수 있다. 따라서 위의 표의 '?'는 중앙값 3의 제곱인 9가 됨을 알 수 있다. 

 따라서 만일 차이가 제곱수가 되면 (중앙값이 k일때) 2k - 1이 된다. 그러나 그렇지 않은 수도 있기에 다른 패턴을 찾아야 한다. 

차이 ( y - x )	이동	횟수
4	1 - 2 - 1	3
5	1 - 2 - 1 - 1	4
6	1 - 2 - 2 - 1	4
7	1 - 2 - 2 - 1 - 1	5
8	1 - 2 - 2 - 2 - 1	5
9	1 - 2 - 3 - 2 - 1	5

 4 이상 9 이하에 속하는 수는 총 6개이다. 이 중 경계값(4와 9)를 빼면 총 4개가 남는데 다른 구간에서도 마찬가지로 정확히 경계값을 뺀 나머지 갯수의 절반 구간 - 이 예시 에서는 각 구간에는 2개의 수가 있다. (5,6) / (7,8) - 으로 나뉘며 첫번째 구간(앞쪽 구간)은 첫 경계값(예시에서는 4)의 횟수 + 1이고, 두번째 구간(뒤쪽 구간)은 끝 경계값(예시에서 9)의 횟수와 같다. 따라서 제곱수가 아니라면 이러한 패턴을 이용해 절반만 탐색해주면 된다.

 

# 코드

import sys
# square_range : 해당 수가 어떤 수의 제곱수인지 판별하는 함수
#  만약 어떤 수의 제곱수가 아니라면 가장 가까운 제곱수의 범위를 찾아 리턴한다
def square_range(num):
    n = 0
    while True:
        if pow(n, 2) < num < pow(n + 1, 2):
            return n, False
        elif pow(n ,2) == num:
            return n, True
        elif pow(n + 1, 2) == num:
            return n + 1, True
        n += 1
        
# solve : 각 수의 범위에 따라 최소 횟수를 출력하는 함수
def solve(num, flag):
    if flag == True: # 이 수가 제곱수인지 아닌지 확인하는 boolean 변수
        ans.append(2 * num - 1)
    else:
    	# 앞쪽 구간 탐색
        for i in range(num ** 2 + 1, num ** 2 + num + 1):
            if i == b - a:
                ans.append(2 * num)
                break
        # 뒤쪽 구간 탐색
        for i in range(num ** 2 + num + 1, (num + 1) ** 2 + 1):
            if i == b - a:
                ans.append(2 * num + 1)
                break
                
tot = int(sys.stdin.readline())
ans = []
for i in range(tot):
    a, b = map(int, sys.stdin.readline().split())
    res1, res2 = square_range(b - a)
    solve(res1, res2)
for i in ans:
    print(i)