1011. Fly me to the Alpha Centauri (Python)

1011번: Fly me to the Alpha Centauri

 

 

풀이

 간단한 규칙을 찾아서 적용하면 된다. 

 

 위의 그림을 보면 규칙을 찾을 수 있다. 4번 작동했을 때 최대로 움직일 수 있는 거리는 6이고, 5번 작동했을 때 최대로 움직일 수 있는 거리는 9이다. 그렇기 때문에 만약 입력으로 주어진 x와 y의 거리가 7~9일 경우에는 최소 5번의 공간이동 장치 작동으로 이동할 수 있음을 알 수 있다.

 

 기준이 되는 거리를 보면 +1 +1 +2 +2 +3 +3 +4 +4 +5 +5.....와 같이 n이 두 번 더해지고 n+1이 두 번 더해지고 n+2가 두 번 더해지고... 하는 식으로 진행됨을 알 수 있다.

 

코드

if __name__ == '__main__':
    T = int(input())  # 테스트 케이스의 개수

    for _ in range(T):
        x, y = map(int, input().split())  # 현재 위치와 목표 위치
        distance = y - x  # 두 위치의 거리
        movement = 0  # 이동한 거리
        res = 0  # 공간이동 장치 작동 횟수

        nextStep = 1  # 이동 거리 증가량
        stepCount = 0  # netStep을 몇 번 더해줬는지 카운트

        while distance > movement:  # 두 위치의 거리가 이동한 거리보다 작거나 같을 때까지
            movement += nextStep  # 이동 거리에 nextStep을 더해 준다.
            res += 1  # 이동한 횟수 증가
            stepCount += 1  # 카운트 변수 증가

            if stepCount == 2:  # nextStep을 두 번 더해줬다면
                stepCount = 0
                nextStep += 1  # nextStep을 1 증가시킨다.

        print(res)