우주선이 번째로 이동한 거리를 라고 했을 때, 수열의 첫째 항과 마지막 항이 1이고 또는 또는 가 되는 상황에서 최소 이동 횟수를 묻는 문제이다!
문제를 푸는 핵심 첫 번째는 바로 의 최댓값에 대해 생각하는 것이다. 수열 는 이웃하는 항과의 차이가 항상 또는 이어야 하므로, 다음과 같은 특징이 성립한다.
의 최댓값이 이라면, 우주선은 적어도 만큼의 거리를 이동했어야 한다!
따라서, 가능한 의 최댓값은 의 정수 부분이 될 것이다.
한편, 위와 같이 우주선이 번의 움직임으로 만큼의 거리를 이동하고 남은 거리 에 대해 생각해 보자. 만약 이라면, 만큼의 이동을 수열 의 적당한 위치에 추가하면 된다! 이때 숫자 은 위의 수열에 항상 포함되어 있으므로, 그 옆자리가 '적당한 위치'가 될 것이다. 다음으로 이라면 만큼의 이동을 수열의 옆에 추가하고 을 만큼 줄이면 된다.
남은 이동 거리 에 대하여, 인 경우 1번만 더 이동하면 되고, 인 경우 번만큼 이동하고 나서, 나머지가 이 아니면 1번 더 이동하면 된다.
확실히 PS를 처음 시작할 때만 해도 백준 Gold의 문제가 많이 어려웠었는데, 지금은 Gold 중 쉬운 문제들은 쉽게 풀리는 것 같아 기분이 좋다!
// BOJ 1011. Fly me to the Alpha Centauri
#include <iostream>
#include <cmath>
void solve() {
int x, y;
// Input
std::cin >> x >> y;
// Answer of (x, y) is equal to (0, y - x).
y -= x;
x = 0;
// If max(k_i) = n, then y >= 1 + 2 + ... + n + (n - 1) + ... + 1 = n * n.
// And it needs (2n - 1) moves.
int n = (int)std::sqrt(y);
int moves = 2 * n - 1;
y -= n * n;
// y is remaining distance.
// If y <= n, one additional move of length y can be attached to appropirate position.
// Otherwise add a move of length n until the remaining distance is less than or equal to n.
moves += (y / n) + (y % n == 0 ? 0 : 1);
// Output
std::cout << moves << std::endl;
}
int main() {
int T;
std::cin >> T;
for (int i=0; i<T; i++) solve();
return 0;
}