[C++] 백준/Gold/1011. Fly me to the Alpha Centauri

Fly me to the Alpha Centauri (백준 1011번)

문제 개요

• 문제 설명:
  우주선이 $x$에서 $y$까지 이동할 때, 이동 거리에 따른 일정한 규칙을 따르는 “점프”를 사용한다.
  문제는 주어진 시작점 $x$와 도착점 $y$ 사이의 거리를 이동하기 위한 최소 점프 횟수를 구하는 것이다.
• 이동 규칙 요약:
  1. 첫 번째 점프는 무조건 1광년, 그 이후 점프 거리는 이전 점프 거리와 같거나 1 증가/감소할 수 있다.
  2. 마지막 점프도 무조건 1광년이다.
  이러한 규칙을 종합하면, 거리를 이동하기 위한 점프 횟수는 일정한 패턴을 따르게 되며,
  (예: 거리 1→ 1회, 2→ 2회, 3→ 3회, 4→ 3회, 5,6→ 4회, 7,8→ 5회, 9→ 5회, …)

---

접근 방법

• 수학적 아이디어:
  기존의 정답 공식은 다음과 같다.
  • $n = \lfloor\sqrt{diff}\rfloor$라 하고,
    • 만약 $diff == n^2$이면 답은 $2n - 1$
    • $n^2 < diff \le n^2 + n$이면 답은 $2n$
    • $n^2 + n < diff < (n+1)^2$이면 답은 $2n + 1$
• 코드 접근:
  이 코드는 위 수식을 직접 사용하지 않고, 누적합 배열을 미리 만들어 놓은 후
  $\text{result} = n + k$ 꼴로 답을 구한다.
  1. 누적합 배열 $v$ 준비:
     • $v[i]$는 $1+2+\cdots+i$의 합이다.
     • $i$는 최대 46341까지 계산하는데, 이는 $\sqrt{2^{31}-1}$ 정도의 범위를 커버하기 위함이다.
  2. 기본 점프 횟수 $n$ 결정:
     • $n = \lfloor \sqrt{diff} \rfloor$로 설정한다.
  3. 추가 점프 횟수 $k$ 결정:
     • $v[n]$는 기본 점프에서 이동한 거리를 의미한다.
     • 남은 거리 $\text{diff} - v[n]$를 커버하기 위해 필요한 추가 점프 횟수 $k$는,
       $v[k]$가 $\text{diff} - v[n]$보다 크거나 같은 최소 $k$로 구한다.
     • 이를 위해 lower_bound 함수를 사용하여 $v$ 배열에서 적절한 $k$를 찾는다.
  4. 최종 답 계산:
     • 최종 점프 횟수는 $n + k$가 된다.

---

코드 전체

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);

    int t; 
    cin >> t;

    // 누적합 배열 v: v[i] = 1 + 2 + ... + i
    // 46342는 충분한 범위를 커버하기 위한 크기 (최대 i가 46341)
    vector<int> v(46342);
    for (int i = 1; i < 46342; i++) 
        v[i] = i + v[i - 1];

    while (t--) {
        int x, y; 
        cin >> x >> y;
        int diff = y - x;

        // 기본 점프 횟수: floor(sqrt(diff))
        int result = sqrt(diff);

        // v[result]는 기본 점프로 이동한 거리
        // 남은 거리는 diff - v[result]
        // 추가로 필요한 점프 횟수 k는, v[k] >= (diff - v[result])가 되는 최소 k
        int k = lower_bound(v.begin(), v.end(), diff - v[result]) - v.begin();

        result += k;
        cout << result << '\n';
    }
}