[기본수학1] Fly me to the Alpha Centauri
2021. 2. 27. 02:12ㆍ백준
이동 거리의 변화는 +1 , 0 , -1 중에서 일어나고 맨 마지막 이동거리는 1이기 때문에, 작동시기별 최대 이동거리에 도달하기 위한 요소들이 생기게 된다.
최대 이동거리가 5라면 1 2 3 4 5 4 3 2 1 의 형태가 기본적으로 존재하게 된다는 뜻. 이 형태의 합을 구하면 n^2 이 된다.
전체 이동거리에서 n^2 로 나올 수 있는 형태를 빼고 나머지를 통해서 잔여 횟수를 더해주면 끝.
잔여 횟수는 0 또는 1 또는 2가 나올 수 있겠다.
9 = 1 2 3 2 1 --- 잔여횟수 0 (3^2)
10 = 1 2 3 2 1 1 --- 잔여횟수 1
11 = 1 2 3 2 2 1 --- 잔여횟수 1
12 = 1 2 3 3 2 1 --- 잔여횟수 1
13 = 1 2 3 3 2 1 1 --- 잔여횟수 2
14 = 1 2 3 3 2 2 1 --- 잔여횟수 2
15 = 1 2 3 3 3 2 1 --- 잔여횟수 2
16 = 1 2 3 4 3 2 1 --- 잔여횟수 0 (4^2)
제출코드
from sys import stdin
import math
test_count = int(stdin.readline())
test_case = []
for i in range(0, test_count):
append_case = list(map(int, stdin.readline().split(" ")))
test_case.append(append_case)
def get_move_count(case):
x = case[0]
y = case[1]
distance = y - x
# print("이동거리")
n = math.floor(math.sqrt(distance))
default_movement = n * n
default_movement_count = 2 * n - 1
# print("제곱근" + str(n))
# print("기본 이동거리" + str(default_movement))
rest_distance = distance - default_movement
add_movement_count = math.ceil(rest_distance / n)
# 최대값인 n만큼의 이동거리
rest_distance % n
# print("이동거리에서 기본 이동거리 뺌" + str(distance - default_movement))
# print("총 이동거리"+str(default_movement_count + add_movement_count))
print(str(default_movement_count + add_movement_count))
for i in range(0, len(test_case)):
get_move_count(test_case[i])