[백준] 1011번 Fly me to the Alpha Centauri - 수학(Python)

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

1011번: Fly me to the Alpha Centauri

사용 알고리즘

사실 사용 알고리즘이라 할 것이 없다. 그냥 수학적 패턴을 찾으면 되는 문제이다.

풀이

우선 1 부터 차례대로 계산 과정을 써보았다.

INPUT	HOW TO	OUTPUT
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
13	1+2+3+3+2+1+1	7
14	1+2+3+3+2+2+1	7
15	1+2+3+3+3+2+1	7
16	1+2+3+4+3+2+1	7
17	1+2+3+4+3+2+1+1	8
18	1+2+3+4+3+2+2+1	8
19	1+2+3+4+3+3+2+1	8
20	1+2+3+4+4+3+2+1	8
21	1+2+3+4+4+3+2+1+1	9
22	1+2+3+4+4+3+2+2+1	9
23	1+2+3+4+4+3+3+2+1	9
24	1+2+3+4+4+4+3+2+1	9
25	1+2+3+4+5+4+3+2+1	9
26	1+2+3+4+5+4+3+2+1+1	10

.

.

.

 

나열을 하고 보니 공간이동 장치의 작동 횟수(out put)이 증가하기 직전의 계산식은 항상 다음과 같은 형태를 띈다는 것을 알게 되었다.

        1 + 2 + ... + k-1 + k + k-1 + ... + 2 + 1             OR              1 + 2 + ... + k-1 + k + k + k-1 + ... + 2 + 1

또한, 1 + 2 + ... + k-1 + k + k-1 + ... + 2 + 1의 식은 항상 어떤 수의 제곱수가 된 다는 사실을 알게되었다.

 

따라서 조건문을 이용해 입력 받은 숫자의 거리차가 위 두식의 어떤 경계에 놓여있는지 판단한다면 쉽게 풀 수 있는 문제이다.

 

Python

def boundary(v):

    i = 1

    bnd = 0

    if v == 1:

        print(1)

        return

    while(1):

        bnd += i*2

        if ((i-1)**2 < v <=bnd):

            print(i*2)

            return

        elif (bnd < v <= (i+1)**2):

            print(i*2+1)

            return

        i+=1

t = int(input())

for i in range(t):

    x, y = map(int,input().split())

    boundary(y-x)