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

1011번: Fly me to the Alpha Centauri

 

문제

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

1011번: Fly me to the Alpha Centauri

 

풀이

문제에서 출발과 도착하기 바로 직전의 이동거리는 1광년만 이동가능하다. 가장 먼저 작동 횟수의 최솟값이기 때문에 이동 거리는 점점 커지다가 줄어야 한다고 생각했다. 출발점과 도착점에서 거리가 1씩 커지면서 출발한다고 생각했고 두 지점 간 거리가 양수인 동안 먼저 (두 지점 간 거리)에서 (이동 거리 × 2) 씩 빼주고 (정답 카운트)를 2씩 올려줬다. 두 점이 아직 만나지 않았다면 (이동 거리)를 1 증가시켰고 만약 두 점이 만나거나 지나치게 되면 (두 지점 간 거리)가 0이 될 때까지 반복문을 돌려주었다. 만약 (두 지점 간 거리)가 음수라면 지나치게 된 것이므로 (이동 거리)만큼 (두 지점 간 거리)를 늘려주고 (정답 카운트)를 1 뺐다. 그리고 (이동 거리)만큼 가면 지나치게 되는 것이므로 (이동 거리)를 1 줄였다. 만약 (두 지점 간 거리)가 양수라면 아직 만나지 못한 것이므로 (이동 거리)만큼 (두 지점 간 거리)를 줄이고 (정답 카운트)를 1 더했다. 그리고 아직 거리가 더 남았을 수 있으니 (이동 거리)를 1 늘려주었다.

예시

예시로 x = 0, y = 10인 경우를 들어보자.
여기서 (이동 거리)란 이동 후 1 늘린 상태로 즉, (다음 이동 거리)다.

처음엔 (두 지점 간 거리) = 10, (이동 거리) = 1, (기계 작동 횟수) = 0 이다.

첫 이동 후 (두 지점 간 거리) = 8, (이동 거리) = 2, (기계 작동 횟수) = 2

두 번째 이동 후 (두 지점 간 거리) = 4, (이동 거리) = 3, (기계 작동 횟수) = 4

세 번째 이동 후 (두 지점 간 거리) = -2, (이동 거리) = 3, (기계 작동 횟수) = 6이 되어 (두 지점 간 거리)가 0보다 작아졌다. (반복문 진입)

(두 지점 간 거리)가 음수이므로 한 점이 이전에 이동한 (3)만큼 돌아가고 (기계 작동 횟수)를 1번 감소시킨다. 그리고 (이동 거리)를 1 감소시킨다.
그럼 (두 지점 간 거리) = 1, (이동 거리) = 2, (기계 작동 횟수) = 5 이 된다.

(두 지점 간 거리)가 양수이므로 한 점이 (이동 거리 = 2)만큼 이동하고 (기계 작동 횟수)를 1 증가시킨다. 그리고 (이동 거리)를 1 증가시킨다.
그럼 (두 지점 간 거리) = -1, (이동 거리) = 3, (기계 작동 횟수) = 6

다시 (두 지점 간 거리)가 음수이므로 한 점이 이전 이동 거리(2)만큼 이동했을 때 지나치게 되니 (이동 거리 = 3)만큼 돌아가고 (기계 작동 횟수)를 1번 감소시킨다. 그리고 (이동 거리)를 1 감소시킨다.
그럼 (두 지점 간 거리) = 2, (이동 거리) = 2, (기계 작동 횟수) = 5

다음으로 (두 지점 간 거리)가 양수이므로 한 점이 (이동 거리 = 2)만큼 이동하고 (기계 작동 횟수)를 1 증가시킨다. 그리고 (이동 거리)를 1 증가시킨다.
그럼 (두 지점 간 거리) = 0, (이동 거리) = 3, (기계 작동 횟수) = 6

(두 지점 간 거리)가 0이 되었으므로 모든 반복문을 탈출한다.

정답은 (기계 작동 횟수)인 6이 된다.

코드

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL), cout.tie(NULL);
  int t;
  cin >> t;
  while (t--) {
    int x, y, ans = 0;
    cin >> x >> y;
    int gap = y - x, k = 1;
    while (gap) {
      gap -= 2 * k;
      ans += 2;
      if (gap <= k) {
        while (gap != 0) {
          if (gap < 0) {
            gap += k;
            ans--;
            k--;
          } else if (gap > 0) {
            gap -= k;
            ans++;
            k++;
          }
        }
      }
      k++;
    }
    cout << ans << '\n';
  }
  return 0;
}