[구현/수학] 백준 1011 Fly me to the Alpha Centauri - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1011번: Fly me to the Alpha Centauri

 

 

 

2. 문제 풀이

 X부터 Y까지의 최소 이동 장치 작동횟수를 구합니다. 이동거리는 1광년부터 시작하며, 그 이후에는 ±1, 0광년만큼 조정이 가능합니다. 단번에 2이상으로 이동거리를 늘리거나 줄일 수 없습니다.

 Y에 도착할 때의 이동거리도 1광년이어야 하며, 이를 만족하기 위해서는 이동거리의 함수가 포물선을 이뤄야 합니다.

 

2022.01.19 - [Algorithm] - [Algorithm] 단골 1번 문제, 구현 / 수학

[Algorithm] 단골 1번 문제, 구현 / 수학

 물리1에 나오는 포물선의 운동방정식 문제와 일맥상통합니다. 이동거리는 포물선을 이루는 2차 함수이며, 속도는 거리함수를 미분한 1차 함수입니다.

 

 

3. 코드

import sys
input = sys.stdin.readline

T = int(input())
for i in range(T):
    x, y = map(int, input().split())
    dist = y-x
    cnt = 0

    while dist > cnt*(cnt+1):
        cnt += 1

    if dist <= cnt**2:
        print(2*cnt-1)
    else:
        print(2*cnt)

 거리(y-x)를 구하고, 이동횟수를 구합니다. 이동횟수는 운동방정식에서 시간(초)으로 여기셔도 됩니다.