> Fly me to the Alpha Centauri > Gold V > #[[수학]] ### 문제 요약 공간이동 장치의 작동 방식은 다음과 같은 규칙을 따릅니다: - 이전 작동 시기에 k광년을 이동했을 때, 다음 작동 시기에서는 k-1, k, 또는 k+1광년만을 이동할 수 있습니다. - 처음 작동할 경우에는 1광년만 이동할 수 있습니다. - 도착 지점에 도달하기 바로 직전의 이동 거리는 반드시 1광년이어야 합니다. x 지점에서 정확히 y 지점으로 최소한의 작동 횟수로 이동하려 할 때, 작동 횟수의 최솟값을 계산해야 합니다. (이때, x는 항상 y보다 작습니다.) ### 해설 공간이동 장치의 전체 이동 과정에서, 한 번의 작동에 최대 M광년을 이동했다고 합시다. 그러면 M광년을 이동하기 이전에 1, 2, ..., M-1광년을 이동한 적이 있어야 하며, 이동한 후에도 M-1, M-2, ..., 1광년을 이동한 적이 있어야 하므로 최소 이동 거리는 $\frac{M(M+1)}{2}+\frac{M(M-1)}{2}=M^2$광년이 됩니다. 이렇게 1, 2, ..., M-1, M, M-1, ..., 2, 1광년 이동하는 과정을 저는 '이상적인 이동'이라고 부르겠습니다. 이동해야 하는 거리를 $d=y-x$광년이라고 할 때, $d>=M^2$가 되는 최소의 M을 찾습니다. 만약 찾은 M에 대해 $d=M^2$를 만족하면, 그것은 이상적인 이동이므로 최소 작동 횟수는 $2M-1$이 됨이 자명합니다. 그렇다면 $M^2<d<(M+1)^2$일 때는 어떨까요? $M^2<d\le M^2+M$이라면, $d-M^2$광년만큼의 이동을 '이상적인 이동' 사이 어딘가에 끼워넣을 수 있고 최소 작동 횟수는 $2M$이 됩니다. $M^2+M< d<M^2+2M+1$이라면 M광년만큼의 이동, 그리고 $d-M^2-M$광년만큼의 이동을 '이상적인 이동' 사이 어딘가에 끼워넣을 수 있고 최소 작동 횟수는 $2M+1$이 됩니다.