[알고리즘 연습]-Fly me to the alpha centauri(python)

1. 문제링크

[fly_me_to_the_alpha] : https://www.acmicpc.net/problem/1011

2. 풀이 전 생각

문제를 읽다가 이해가 잘 안되서 여러번 읽었고, 수학적인 규칙을 찾으려고 많은 고민을 했다.

이동 거리 k

행성 거리 n

이동 횟수 i

n       k                i     

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    2    2     1   1 (5)

8       1    2    2     2   1 (5)

9       1    2    3    2    1 (5)

10     1    2    3    2     1    1 (6)

11     1    2    3    2     2    1 (6)

12     1    2    3    3    2     1 (6)

3. 풀이

t = int(input("테스트 케이스:"))
result = []

for i in range(t):
    x, y = map(int, input("숫자 입력: ").split(","))
    z = y - x
    v = int(z**(1/2)) + 1
    down = (v - 1) * (v - 1)
    up = v * v
    stand = (up + down) / 2

    if stand > z:
        result.append(v * 2 -2)
    else:
        result.append(v * 2 -1)

print(result)

문제를 직접 적으면서 거리가 늘어날때 마다 이동최솟값을 적으면서 규칙을 찾아보았다. 제가 알아낸 규칙은 해당 거리의 제곱근은 인접한 제곱수의 절반을 기준으로 짝수와 홀수가 나누어져 있다.
(예를 들어 7의 제곱근은 2.xx이고 이 수의 인접 제곱수는 4와 9가 있는데, 이를 더해서 나누게 되면 6.5가 나옵니다. 6.5를 기준으로 크다면 홀수 작다면 짝수가 나오게 됩니다.

4. 풀이하면서 고민했던 점

이 문제는 규칙이 까다로워서 찾는데 많은 시간을 소비했고, 답을 찾는데 집중한 것 같다.

5. 문제를 풀고 난 소감

문제가 어려워서 효율적인 방법을 신경쓰기 보다 문제를 푸는데 의의를 두었고, 계속 연습해서 문제 해결능력을 기르는데 집중해야 될 것 같다.