💻 문제: Fly me to the Alpha Centauri

문제 소개 🧐

x 지점에서 y 지점으로 공간이동 장치를 이용해 최소한의 작동 횟수로 이동하는 문제다. 공간이동 장치는 이전에 k 광년을 이동했다면, 다음에는 k-1, k, 또는 k+1 광년만큼 이동할 수 있다. 첫 이동은 1광년이며, 목표 지점 도착 직전의 이동 거리는 반드시 1광년이어야 한다.

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
2 초 512 MB 105104 33004 26017 32.466%

입력 📝

  • 입력의 첫 줄에는 테스트케이스의 개수 T가 주어진다.
  • 각각의 테스트 케이스에 대해 현재 위치 x 와 목표 위치 y 가 정수로 주어지며, x는 항상 y보다 작은 값을 갖는다. (0 ≤ x < y < 231)

출력 📤

  • 각 테스트 케이스에 대해 x지점으로부터 y지점까지 정확히 도달하는데 필요한 최소한의 공간이동 장치 작동 횟수를 출력한다.

Idea: 수학적 패턴 찾기 ✨

Idea

이 문제는 이동 거리에 대한 규칙을 분석하면 수학적 패턴을 발견할 수 있다. 이동 횟수를 최소화하려면, 이동 거리를 1씩 늘려가다가 특정 시점부터 다시 1씩 줄여 목표 지점에 도착하는 대칭적인 구조가 가장 효율적이다.

예를 들어, 이동 거리가 1, 2, 3, 2, 1과 같이 증가했다가 감소하는 패턴을 생각할 수 있다.

  • 총 이동 거리 d = y - x
  • 최대 이동 거리를 n이라고 할 때, 1부터 n까지의 합의 두 배와 비슷한 패턴을 보인다.
  • 이동 횟수와 거리 사이의 관계를 분석하면 다음과 같은 규칙을 도출할 수 있다.
    1. 먼저, 이동 거리 d의 제곱근을 정수 형태로 구한다. n = int(sqrt(d))
    2. d가 n^2과 같다면, 이동 횟수는 2n - 1이 된다. (예: d=9, n=3, 횟수: 1-2-3-2-1 -> 5회 = 2*3-1)
    3. d가 n^2보다 크고 n^2 + n보다 작거나 같다면, 이동 횟수는 2n이 된다.
    4. d가 n^2 + n보다 크다면, 이동 횟수는 2n + 1이 된다.

이러한 수학적 규칙을 이용하면, 복잡한 시뮬레이션 없이 간단한 계산만으로 최소 작동 횟수를 구할 수 있다.

Code

import math
import sys

T = int(sys.stdin.readline().rstrip())

for _ in range(T):
    x, y = map(int, sys.stdin.readline().split())
    d = y - x
    n = int(math.sqrt(d))
    
    if d == n ** 2:
        print(2 * n - 1)
    elif n ** 2 < d <= n ** 2 + n:
        print(2 * n)
    else:
        print(2 * n + 1)

Result

  • 결과: 성공! 🎉
  • 그리디하게 이동 거리를 늘렸다가 줄이는 대칭적 패턴을 기반으로 수학적 규칙을 찾아 해결했다.

배운 점 및 개선할 부분 🤔

  • 패턴 인식의 중요성: 복잡한 규칙을 가진 문제일수록, 간단한 예시들을 통해 패턴을 분석하고 일반화하는 능력이 중요하다는 것을 다시 한번 느꼈다.
  • 수학적 접근: 모든 경우를 시뮬레이션하는 대신, 문제의 핵심 원리를 파악하여 수학적으로 접근하면 훨씬 효율적인 풀이가 가능하다. 이 문제는 그리디한 선택이 최적해로 이어지는 구조를 수학적으로 증명하고 풀이법을 도출하는 좋은 예시이다.
  • 제곱근 활용: 이동 거리와 횟수 사이의 관계가 제곱근과 밀접한 관련이 있음을 파악하는 것이 문제 해결의 핵심이었다.

겉보기에는 복잡한 시뮬레이션 문제처럼 보이지만, 그 안에 숨겨진 수학적 규칙을 발견하면 간결하게 해결할 수 있다.

⁂