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

• Problem Link : https://www.acmicpc.net/problem/1011

문제

• x지점에서부터 y지점으로 이동하는데 k광년씩 이동한다.
• 이전 작동 시기에 k 광년을 이동했다면 다음 작동 시기에 k-1, k, k+1 광년만큼 이동할 수 있다.
• 안전성을 위하여 y 지점에 도착하기 바로 직전의 이동거리는 반드시 1광년으로 한다.

입력

• 첫째 줄, 테스트 케이스 T
• 둘째 줄, 각각의 테스트 케이스의 현재 위치 x 와 목표 위치 y

출력

• 필요한 최소한의 공간이동 장치 작동 횟수를 출력

풀이

문제에서 요구하는 것은 최소한의 공간이동 장치 작동 횟수이므로 결국 한 번 이동할 때 최대로 이동을 해야만 장치 작동 횟수의 최소값을 구할 수 있다. 따라서 최대한 이동할 거리를 늘리다가 점차 다시줄여 1광년으로 도착 지점에 도달한다면 해당 횟수가 최소한의 횟수 임을 알 수 있다.

• 위 표를 참고하면 x부터 y까지의 거리는 $n^2$이므로 $y-x$값이 $n^2$를 넘기지 않는 n의 최대값을 찾는다.

• 거리가 $n^2$으로 딱 나누어떨어지지 않으면 해당 값은 n을 넘기지 않는 선에서 최대 크기 n으로 쪼개서 사이에 넣어줄 수가 있다.

• 예를 들어, 거리가 47이라고 해보면 $n=6$ 일 때 36 광년을 채워줄 수 있다.

• 그럼 이때 남은 광년이 11년이고 11년을 n보다 작거나 같은 광년으로 최대한 크게 쪼개 줄 수 있다. 즉, 11을 6으로 나누면 몫이 1이고 나머지가 5이므로 6광년, 5광년으로 쪼갤 수 있고 해당 값은 우리가 기존에 만들었던 광년들 사이에 삽입해 줄 수가 있다.

• 따라서 이 경우에 장치의 작동 횟수는 기존 $n^2$을 이동하는데 걸린 $2n -1$번에 남은 광년을 쪼개서 넣은 횟수, 즉 (남은거리/n)을 소수 첫째자리에서 올림해준 값을 더해주면 된다.

  남은 광년을 n보다 큰 광년으로 쪼개지 않는 이유는?
  n보다 큰 광년이 삽입되기 위해서는 최소한 n이 두 번 나와야 하는데 n이 한 번 나오기 때문에 n보다 큰 값으로 쪼갤 수 없다.

  그럼 n+1까지 한 다음에 n+1로 남은 광년을 쪼개는게 더 적은 횟수 아닌가요?
  아까 위에서 말했듯이 거리($y-x$)보다 작거나 같은 $n^2$을 만족시키는 n의 최대값을 찾기 때문에 만약 n+1까지 증가시키게 되면 거리를 넘어가게 된다.

• 위와 같은 방법으로 두 지점 간의 거리를 넘기지 않는 $n^2$을 만족시키는 n의 최대값을 찾는다면 실제 이동장치의 작동 횟수를 구할 수 있다.
• 이 때 나머지가 있을때는 횟수를 1 증가시켜야 하는데 따로 나머지가 있는지 확인하기보다 math 모듈의 ceil(올림) 함수를 이용해서 나머지가 있으면 자동으로 횟수가 1 증가되도록 코딩했다.

코드

import math
import sys

input = sys.stdin.readline

ans = []
T = int(input())
for _ in range(T):
    x, y = map(int, input().split())
    n = 1
    distance = y - x
    while n**2 <= distance:
        n += 1
    n -= 1

    print((n * 2 - 1) + math.ceil((distance - (n**2)) / n))