백준 알고리즘 1011 (Fly me to the Alpha Centauri) - python

[ 문제 ] 백준 알고리즘 1011 (Fly me to the Alpha Centauri) - python

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

1011번: Fly me to the Alpha Centauri

 

입력 x와 입력 y의 거리에 따른 규칙을 찾아 해결하는 문제이다.

규칙에 따라 표로 정리해보면, 아래와 같다.

 

거리	이동	횟수	횟수 증가 시점	수식
1	1	1
2	11	2
3	111	3	3 이하는 그대로 출력
4	121	3	2의 제곱	2*2-1
5	1211	4
6	1221	4	2의 제곱 + 2	2*2
7	12211	5
8	12221	5
9	12321	5	3의 제곱	2*3-1 (=2*2+1)
10	123211	6
11	123221	6
12	123321	6	3의 제곱 + 3	2*3
13	1233211	7
...	...	...	...	...

 

내가 발견한 규칙은 (N>=2일 때) 

1. N의 제곱 또는 N의 제곱 + N의 거리 이후 횟수가 증가한다는 것

2. N의 제곱일 때는 2 * N - 1, N의 제곱 + N이하는 2 * N, 그 이후로는 2 * N + 1의 횟수를 갖는 것

 

이 규칙들을 이용하면, N과 거리의 관계만으로 코드를 구현할 수 있다.

 

[Code]

import math
T = int(input())
for _ in range(T):
    x, y = map(int, input().split())
    diff = int(y - x)
    if diff <= 3:
        print(diff)
    else:
        n = int(math.sqrt(diff))
        if diff == n ** 2:
            print(2*n-1)
        elif n ** 2 < diff <= n ** 2 + n:
            print(2*n)
        else:
            print(2*n+1)