문제 요약:

테스트 케이스 T가 처음에 주어지고, 그 횟수만큼 최소 이동 횟수를 구하면 되는 문제.

이동 로직:

• 이전 시기에 k만큼 움직였다면 다음 턴에 k-1, k, k+1만큼 이동할 수 있다.
• 초기에는 -1, 0, 1 선택 가능하나(사실상 1로 시작하는것), 마지막에는 이동거리가 1로 고정되어야한다.

문제 풀이

• 마지막에 1로 움직일 거리가 고정되어야하므로 직전에는 0, 1, 2만큼 움직여야 가능하나, 0만큼 움직이는 건 무의미하므로 1이나 2로 끝나야 함.
• 그렇다면 마지막에서 두 번쨰는 최대 3까지 이동, 세 번째는 최대횟수 4...이러한 패턴이 있다
• 각각 지점에서 최대 이동거리를 취했다가 다시 돌아온다고 가정하면 1->2->3->...n->n-1->...->2->1과 같이 된다.
• 그리고 저런 식의 패턴은 합이 $n^2$이고, 한 턴에 이동한 최대거리가 최종적으론 n이 되는것이다.
• 저런 패턴에서 1이나 2를 마지막에 추가하여 가능한 길이를 더 만들 수도 있다.1->2->3->2->2->1->1...이런 식으로

문제 상황을 분석하자면 위와 같은 느낌이다.
예시를 적용해보자면 9는 1->2->3->2->1로 저기서의 n은 3이며 2n+1번만큼의 이동에서 최소 이동횟수를 갖는다. 제곱수의 경우 저 로직에서 벗어나지 않을 것으로 보인다. 그렇다면 제곱수가 아닌 경우, 즉 $n^2+\alpha$와 같은 수에서 저게 어떻게 작동되는지 알면 사실상 해결되었다고 봐도 될 것으로 보임. 1이나 2 추가하는 것은 그닥 문제가 아니라고 했는데, 사실 n(최대 이동거리) 이 친구보다 $\alpha$가 같거나 작으면 한 번만 추가해도 되고, 그렇지 않다면 쪼개야 하는 것이다. 쪼갤 때는 n이하의 수들로 분할하면서, 이동 횟수는 최소한이 되도록 쪼개야 할 것이다. 우리가 구해야하는 건 최소 횟수인데, 만약 쪼갠다고 할 때 최대로 쪼갠다면 1->2->...n->n->n->...와 같이 추가될 수 있으므로 $\alpha$를 n으로 나누면 복잡한 로직 없이 해결될 것 같다.

#include <cmath>
#include <iostream>

using namespace std;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  long long x, y;
  long long move, max;
  // 이동 횟수와 최대 이동거리
  cin >> t;
  for (int i = 0; i < t; i++) {
    cin >> x >> y;
    move = 0;
    max = 0;
    while (max * max <= y - x)
      max++;
    //y-x는 거리, 제곱수로 표현 가능한 최대 max를 찾는다
    max--;
    move = 2 * max - 1;
    long long alpha = y - x - max * max;
    //거리에서 제곱수 말고 남는 부분.
    alpha = (long long)ceil((double)alpha / (double)max);
    //최대 횟수로 나눠준 후 올림을 통해 정수인 횟수로 나오게 해야한다. 
    move += alpha;
    cout << move << '\n';
  }
}

구현은 위와 같이 했다. ceil은 올림을 해주는 함수이다. 일반적으로 round를 쓸 일이 많은 것 같은데, 이동 횟수 자체는 반올림으로 떨어지게 하는 것이 더 처리에 불편할 것 같으므로 위와 같이 ceil을 쓰는 게 더 간단해보이는 부분...