[BOJ 1011] Fly me to the Alpha Centauri

https://www.acmicpc.net/problem/1011

 

문제 개요
이 문제는 우주선이 현재 위치에서 목표 위치로 이동할 때, 주어진 규칙에 따라 최소한의 이동 횟수를 구하는 문제이다. 이동하는 규칙은 다음과 같다:

1. 우주선은 매번 이동할 때마다 "최대 속도"가 1만큼 변할 수 있다. 이 최대 속도는 1부터 시작하며, 속도는 양수만 가능하다.
2. 우주선이 목표 위치에 도달하기 전까지 속도를 감소시킬 수 없다. 즉, 우주선이 목표 위치에 도달할 때까지 속도는 증가하거나 일정하게 유지될 수 있다.
3. 목표 위치에 도달한 순간에는 속도가 0이 된다.

입력
입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스는 두 정수 (x)와 (y)로 이루어져 있으며, 이는 우주선의 현재 위치와 목표 위치를 나타낸다. (0 ≤ x < y ≤ (2^{31}-1))

출력
각 테스트 케이스에 대해, 목표 위치에 도달하기 위한 최소 이동 횟수를 출력한다.

문제 풀이

이 문제를 풀기 위해서는 특정 패턴을 찾는 것이 중요하다. 먼저, 거리 (d = y - x)를 계산한 뒤, 이 거리에 도달하기 위해 우주선이 취할 수 있는 이동 패턴을 살펴봐야 한다.

1. 거리 분석

우주선이 움직일 수 있는 패턴은 다음과 같다:

• 시작할 때 속도를 1씩 증가시키다가, 일정 속도로 유지한 후, 다시 1씩 감소시키며 목표 위치에 도달한다.
• 증가하는 속도 구간과 감소하는 속도 구간의 대칭성을 고려해야 한다.

2. 움직임 패턴

• 거리 (d)에 대해, 속도를 증가시켜서 움직일 수 있는 최대 거리와 그에 필요한 횟수를 계산한다.
• 그 후, 남은 거리만큼 추가적인 이동이 필요한지 판단한다.

이동 패턴 정리

• (n^2 \leq d < (n+1)^2) 일 때, 이 거리를 최소한의 이동으로 도달할 수 있는 패턴은:
  • (d = n^2) -> 총 2n - 1번 이동
  • (n^2 < d \leq n^2 + n) -> 총 2n번 이동
  • (n^2 + n < d < (n+1)^2) -> 총 2n + 1번 이동

이를 바탕으로 C++ 코드를 작성하였다.

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    int t;
    cin >> t;

    while (t--) {
        long long x, y;
        cin >> x >> y;
        long long d = y - x;
        long long n = sqrt(d);

        if (d == n * n) {
            cout << 2 * n - 1 << endl;
        } else if (n * n < d && d <= n * n + n) {
            cout << 2 * n << endl;
        } else {
            cout << 2 * n + 1 << endl;
        }
    }

    return 0;
}

코드 설명

1. 거리 계산: 각 테스트 케이스에 대해 목표 위치와 현재 위치의 거리를 계산한다.
2. 최소 이동 횟수 계산: 주어진 거리 (d)에 대해 최소 이동 횟수를 계산한다. 이때, 거리의 제곱근을 기준으로 3가지 경우로 나누어 결과를 구한다.
   • (d = n^2) 일 경우: 2n - 1번 이동
   • (n^2 < d \leq n^2 + n) 일 경우: 2n번 이동
   • (n^2 + n < d < (n+1)^2) 일 경우: 2n + 1번 이동

결론

이 문제는 수학적 패턴을 분석하는 과정이 중요하다. 각 테스트 케이스에서 목표 위치에 도달하기 위한 최소한의 이동 횟수를 구하기 위해 제곱근과 그 범위에 따른 계산이 핵심이다. 위의 알고리즘을 사용하면 효율적으로 문제를 해결할 수 있다.