[백준] 1011: Fly me to the Alpha Centauri 파이썬 풀이

1011번: Fly me to the Alpha Centauri

문제설명

어떤 이동거리에 대해 움직이는 최소 횟수를 구하는 문제입니다. 

이동 방법은 1칸 점프 부터 시작해서, n 번째에 x칸 점프 했다면 n+1 번째는 x-1 or x or x+1 칸 점프할 수 있습니다.

끝 지점은 반드시 1칸 점프로 도착해야합니다.

 

풀이과정

1. 이동거리가 n일 때, 최소 이동횟수를 구해봤습니다.

2. 위를 구해보니, 특정 이동 횟수에 대해 갈 수 있는 최대 거리의 규칙이 보였습니다.

3. 이동횟수 i, i 일 때 이동할 수 있는 최대거리 x

4. 최초로 i에 대한 x가 이동거리 <= x 인 i r가 답입니다. (이동거리 <= x 인 i의 최솟값)

파이썬코드

import sys
readline = sys.stdin.readline

T = int(input())
for _ in range(T):
    S, E = map(int, readline().split())
    n = E-S

    i, x, y = 1, 1, 1
    while not n<=x: # i 횟수에 갈 수있는 최대거리 x가 n 이상인걸 찾음
        x = x + y
        i += 1
        if i%2==0:
            y += 1

    print(i)