백준 알고리즘 1011 - python Python

[ 문제 ] 백준 알고리즘 1011 - python (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
14 1233221 7
15 1233321 7
16 1234321 7 4의 제곱 2*4-1(= 2*3+1)
----------------------------------
17 12343211 8
. . .
. . .
. . .


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

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

2. N의 제곱일 때는 2 * N - 1N의 제곱 + 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)



덧글

댓글 입력 영역