[BOJ / 파이썬] 1011번: Fly me to the Alpha Centauri

백준 / BOJ / Python / 파이썬

문제 링크 : https://www.acmicpc.net/problem/1011

1011번: Fly me to the Alpha Centauri

단계 : 기본 수학 1

알고리즘 분류 : 수학

 

풀이: 

 문제 내용을 읽어볼 경우 풀면서 신경써야할 부분을 요약하자면 다음과 같다.

1) 첫 이동은 1만 가능, 마지막 이동도 1만 가능

2) 나머지 이동은 이전 이동의 인접한 숫자만큼만 가능

 

문제를 풀기 위해 앞에서부터 몇개를 직접 풀어보자

숫자	풀이	횟수	해당 횟수가 나오는 길이
1	1	1	1
2	1 + 1	2	1
3	1 + 1 + 1	3	2
4	1 + 2 + 1	3
5	1 + 2 + 1 + 1	4	2
6	1 + 2 + 2 + 1	4
7	1 + 2 + 2 + 1 + 1	5	3
8	1 + 2 + 2 + 2 + 1	5
9	1 + 2 + 3 + 2 + 1	5
10	1 + 2 + 3 + 2 + 1 + 1	6	3
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	4
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

 직접 식을 적어보면서 알 수 있던  점은 길이가 늘어나는 위치이다. 특정 길이가 지속되는 기간은 1, 1, 2, 2, 3, 3... 처럼 증가한다는 것이다. 더 자세히 들여다보면 1, 1, 2, 2, 3, 3, 4, 4...를 홀수번째까지 더했을 때 나오는 것이 모두 어떤 수의 제곱수(1, 4, 9, 16...)임을 이용하는 것이다. 이를 이용하여 문제를 풀 수 있다.

 

코드

from math import floor, sqrt

t = int(input())

for i in range(t):
    s, e = map(int, input().split())
    dis = e - s
    n = floor(sqrt(dis - 1))

    if pow(n, 2) < dis <= pow(n, 2) + n:
        print(2 * n)
    else:
        print(2 * n + 1)