[백준] 1011 (Fly me to the Alpha Centauri)
#PS#BOJ#tier:g5#math

[백준] 1011 (Fly me to the Alpha Centauri)

문제 요약

공간이동 장치의 작동 방식은 다음과 같은 규칙을 따릅니다:

  • 이전 작동 시기에 k광년을 이동했을 때, 다음 작동 시기에서는 k-1, k, 또는 k+1광년만을 이동할 수 있습니다.
  • 처음 작동할 경우에는 1광년만 이동할 수 있습니다.
  • 도착 지점에 도달하기 바로 직전의 이동 거리는 반드시 1광년이어야 합니다.

x 지점에서 정확히 y 지점으로 최소한의 작동 횟수로 이동하려 할 때, 작동 횟수의 최솟값을 계산해야 합니다. (이때, x는 항상 y보다 작습니다.)

해설

공간이동 장치의 전체 이동 과정에서, 한 번의 작동에 최대 M광년을 이동했다고 합시다. 그러면 M광년을 이동하기 이전에 1, 2, ..., M-1광년을 이동한 적이 있어야 하며, 이동한 후에도 M-1, M-2, ..., 1광년을 이동한 적이 있어야 하므로 최소 이동 거리는 M(M+1)2+M(M−1)2=M2\frac{M(M+1)}{2}+\frac{M(M-1)}{2}=M^2광년이 됩니다. 이렇게 1, 2, ..., M-1, M, M-1, ..., 2, 1광년 이동하는 과정을 저는 '이상적인 이동'이라고 부르겠습니다.

이동해야 하는 거리를 d=y−xd=y-x광년이라고 할 때, d>=M2d>=M^2가 되는 최소의 M을 찾습니다. 만약 찾은 M에 대해 d=M2d=M^2를 만족하면, 그것은 이상적인 이동이므로 최소 작동 횟수는 2M−12M-1이 됨이 자명합니다. 그렇다면 M2<d<(M+1)2M^2<d<(M+1)^2일 때는 어떨까요?

M2<d≤M2+MM^2<d\le M^2+M이라면, d−M2d-M^2광년만큼의 이동을 '이상적인 이동' 사이 어딘가에 끼워넣을 수 있고 최소 작동 횟수는 2M2M이 됩니다. M2+M<d<M2+2M+1M^2+M< d<M^2+2M+1이라면 M광년만큼의 이동, 그리고 d−M2−Md-M^2-M광년만큼의 이동을 '이상적인 이동' 사이 어딘가에 끼워넣을 수 있고 최소 작동 횟수는 2M+12M+1이 됩니다.