[기본수학1] Fly me to the Alpha Centauri

2021. 2. 27. 02:12백준

 

1011번: Fly me to the Alpha Centauri

우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행

www.acmicpc.net

이동 거리의 변화는 +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])