1011_Fly me to the Alpha Centauri

입력

첫째 줄에 테스트케이스 개수(T) 입력
둘째 줄부터 T+1번째 줄까지 순서대로 출발점(x)과 도착점(y) 입력

출력

출발점에서 도착점까지 도달하기 위한 최소 기계 작동 횟수를 출력

조건

• 처음 출발과 마지막 도착은 무조건 1씩 이동
• 다음에 움직일 수 있는 거리는 k-1, k, k+1

풀이

점 사이의 거리가 2이하일 경우 거리에 따라 작동 횟수가 동일
점 사이의 거리가 2초과일 경우 작동 횟수가 4부터 2씩 증가

1. 점 사이의 거리가 2이하일 경우 거리에 따라 작동 횟수 설정

    if dist <= 2: ans = dist

2. 점 사이의 거리가 2초과일 경우 작동 횟수 4부터 2씩 증가시키며 거리 비교

    else:
        tmp = 2
        inc = 4

        while 1:
            if tmp+inc+2 <= dist:
                tmp += inc
                inc += 2
            else: break

3. 작동 횟수가 3,4 - 2번 / 5,6 - 3번처럼 두 가지가 같은 반복을 가지기 때문에 이를 판별해주기 위해 현재 고려하고 있는 작동 횟수/2한 값을 더한 거리가 출발점과 도착점 사이의 거리보다 작으면 작동 횟수-1, 그렇지 않으면 현재 작동 횟수를 정답으로 설정

        if tmp + inc//2 >= dist: ans = inc-1
        else: ans = inc

Python3 기준 592ms이 결렸는데 80ms가 소모된 다른 코드를 참조한 결과 제곱근을 활용해 작동 횟수를 판별하였다. 더 나은 공식을 찾아보도록 더 머리를 만들어보자.

전체 코드

Fly me to the Alpha Centauri