[BOJ 1011] Fly me to the Alpha Centauri

1011번: Fly me to the Alpha Centauri

문제 분석

• 이동 해야 하는 거리 d = y - x, 이동 장치 작동 횟수 최솟값 : m
• 순간 이동은 1씩 증가시킬 수 있다.
• d = 1 ( m = 1 ), d = 2 = 1 + 1 ( m = 2 )
  d = 3 = 1 + 1 + 1, d = 4 = 1 + 2 + 1 ( m = 3 )
  d = 5 = 1 + 2 + 1 + 1, d = 6 = 1 + 2 + 2 + 1 ( m = 4 )
  ....
  1 + 2 +  ... + n-1 +  n-1 + n-2 ... + 1 + 1 ( m = 2n-1 )
  ..
  1 + 2 +  ... + n-1 +  n-1 + n-1 ... + 2 + 1 ( m = 2n-1 )
  1 + 2 +  ... + n-1 +  n + n-1 ... + 2 + 1 ( m = 2n-1 )
  1 + 2 +  ... + n-1 +  n + n-1 ... + 2 + 1 + 1 ( m = 2n )
  ....
  1 + 2 +  ... + n-1 + n + n + n-1 ... + 2 + 1 ( m = 2n )
  
  ∴ m이 2n - 1 혹은 2n 인 경우의 가짓수는 2n이다. -> 2n씩 증가 : { 2, 6, 12, 20 .... }
• { 2 = 2(1), 6 = 2(1+2), 12 = 2(1+2+3), 20 = 2(1+2+3+4), .... , 2* ∑₍ᵢ₌₁..ₙ₎ i = 2 *[( n+1)n / 2 ] = n² + n }

풀이 방식

• n² + n 의 수열 정수형 배열로 저장
• d = y - x
• "(n-1)² + (n-1) = n² - n ≤ d ≤ n² + n" 인 n을 반복문을 이용해 찾는다.
  • d ≤ n² : m = 2n - 1
  • d > n² : m = 2n

#include <iostream>

#define MAX 47000 // >= 2³¹ + √(2³¹) 

using namespace std;

int t, x, y;
long long d;
long long arr[MAX + 1];

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

    for (long long i = 1; i <= MAX; i++) {
        arr[i] = (i * i + i);
    }
    cin >> t;
    while (t--) {
        cin >> x >> y;
        d = y - x;
        if (d == 1) {
            cout << 1 << "\n";
            continue;
        }
        for (long long i = 1; i <= MAX; i++) {
            if (d > arr[i - 1] && d <= arr[i]) {
                if (d <= i * i) cout << 2 * i - 1 << '\n';
                else cout << 2 * i << '\n';
                break;
            }
        }
    }

    return 0;
}

느낀 점 

• 문제를 풀기전에 문제를 분석하며 분명 규칙이 있다는 것을 느꼈고, 그것을 파악하는데에는 오랜시간이 걸리진 않았다.
• 하지만 규칙을 일반화하기 어려웠고 일반화하는 데에 시간이 오래 걸렸다. (n² + n)
• 규칙을 파악하고 코드로 옮기는 건 금방 했다.
• 문제를 분석하여 규칙을 찾아 일반화하는 것이 얼마나 중요한 지 느끼게 해주는 문제였다.

시간 복잡도 : O (MAX = 47000 ) , 47000 (>= 2³¹ + √(2³¹) )