[백준 1011] Fly me to the Alpha Centauri (C#, C++) - soo:bak

문제 링크

1011번 - Fly me to the Alpha Centauri

설명

어떤 우주선이 k 만큼 이동하였다면, 그 다음에는 k - 1, k , k + 1 중 한 경우로만 이동할 수 있을 때,

입력으로 주어지는 현재 위치 x 에서 목표 위치 y 로 최소한의 횟수로 이동하는 경우를 구하는 문제입니다.

탐색을 활용하여 문제를 풀이할 수도 있지만,

시간 복잡도를 고려하였을 때 가장 효율적인 풀이 방법은 수학적 일반항을 구하여 풀이하는 것입니다.

문제의 조건에 따르면 우주선은 이전 이동거리의 -1 , 0, +1 중 하나로 이동할 수 있습니다.

이 때, 최대한 효율적으로 이동하기 위한 방법은 이동 거리를 늘리는 부분 과 이동 거리를 줄이는 부분 을 나누고,

이동 거리를 늘리는 부분에서는 최대한으로 거리를 늘리고 , 이동 거리를 줄이는 부분에서는 최대한으로 거리를 줄이는 것입니다.

가장 처음에는 -1 , 0, +1 중에서 +1 만이 적절한 선택이므로,

이동 거리를 1 에서부터 최대한 늘리는 경우는 1 - 2 - 3 - ... - k 과 같은 경우입니다.

이 때, 총 이동거리는 1 + 2 + 3 + ... + (k - 1) + k 이 되므로, 공차가 1 인 등차 수열을 이룹니다.

즉, 최대한 늘리는 경우에서의 총 이동거리는 k(k + 1) / 2 가 됩니다.

이동 거리를 줄이는 부분에 대해서는 문제의 요구 조건 중 마지막 이동 거리는 1 이어야 한다 는 조건을 확인해야 합니다.

따라서, 현재 위치 x 와 목표 위치 y 사이에서 이동 거리를 늘리는 부분 과 이동 거리를 줄이는 부분 을 적절한 위치에서 나누는 것이 중요합니다.

이런 특징을 이용하여, 현재 위치 x 와 목표 위치 y 사이의 거리를 d 로, 거리 d 의 제곱근을 n 으로 가정하였을 때,

문제의 이동 거리 제한이 -1 , 0, +1 중 하나라는 조건에 따라, n 은 거리 d 를 위해 소모되는 이동 횟수의 근사치가 됩니다.

예를 들어, 거리가 1 , 4 , 9 , 16 인 경우를 생각해 보면, 이들은 각각 1², 2², 3², 4²와 같이 제곱수입니다.

이 때, 문제의 조건에 따라 각 경우에 필요한 최소 이동 횟수는 각각 1, 3, 5, 7 이 됩니다.

이 값들은 각각 (2 * 1 - 1), (2 * 2 - 1), (2 * 3 - 1), (2 * 4 - 1)로, 거리의 제곱근의 2 배에서 1 을 뺀 값과 일치합니다.

따라서, n 을 거리 d 에 대한 이동 횟수의 근사치 로 가정하고, 다음과 같은 경우로 나누어 봅니다.

이동을 시작할 때,

1. d 가 (n * n) 와 같을 때
   
   • 이 경우, 이동 거리는 n * n 과 같습니다.
     
   • 즉, 거리가 d 이자 n * n 인 위치에 도달하려면, 거리를 늘릴 때 n - 1 번 이동하고, 거리를 줄일 때 n 번 이동해야 합니다.
     
   • 따라서, 최소 이동 횟수는 (2 * n) - 1 이 됩니다.
     
2. d 가 (n * n) 보다 크고 (n * n) + n 보다 작거나 같을 때
   
   • 이 경우, 해당 d 의 범위에 도달하기 위해서는, 거리를 늘릴 때 n 번 이동해야 하며, 거리를 줄일 때 n 번 이동해야 합니다.
     
   • 따라서, 최소 이동 횟수는 (2 * n) 이 됩니다.
     
3. d 가 (n * n) + n 보다 클 때
   • 이 경우, 해당 d 의 범위에 도달하기 위해서는, 거리를 늘릴 때 n + 1 번 이동해야 하며, 거리를 줄일 때 n 번 이동해야 합니다.
     
   • 따라서, 최소 이동 횟수는 (2 * n) + 1 이 됩니다.
     

---

Code

[ C# ]

namespace Solution {
  class Program {
    static void Main(string[] args) {

      var cntCase = int.Parse(Console.ReadLine()!);

      for (int c = 0; c < cntCase; c++) {
        var input = Console.ReadLine()!.Split(' ');
        var x = long.Parse(input[0]);
        var y = long.Parse(input[1]);

        var d = y - x;
        var n = (long)Math.Sqrt(d);

        if (n * n == d)
          Console.WriteLine(2 * n - 1);
        else if (d > n * n && d <= n * n + n)
          Console.WriteLine(2 * n);
        else
          Console.WriteLine(2 * n + 1);
      }

    }
  }
}

[ C++ ]

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int cntCase; cin >> cntCase;

  for (int c = 0; c < cntCase; c++) {
    ll x, y; cin >> x >> y;

    ll d = y - x;
    ll n = sqrt(d);

    if (n * n == d)
      cout << 2 * n - 1 << "\n";
    else if (d > n * n && d <= n * n + n)
      cout << 2 * n << "\n";
    else
      cout << 2 * n + 1 << "\n";

  }

  return 0;
}