백준[1011] Fly me to the Alpha Centauri

문제 설명

문제 링크

http://icpc.me/1011

1011번: Fly me to the Alpha Centauri

풀이

규칙을 찾으면 되는 문제다.

어떤 거리만큼 가장 짧은 거리로 가려면 한 번에 많은 거리를 움직여야 한다. 한 번에 움직이는 거리가 최대가 되는 상황을 잘 구하면 된다.

만약 한번에 k만큼 움직인다면, k만큼 움직이기 위해서는 1 2 3 4 .. k k-1 k-2 .. 1 이런 식으로 움직여야 할 것이다.

이때 1 + 2 + 3 + 4 + .. + k + k-1 + k-2 + .. + 1는 k(k+1)/2 + k(k-1)/2로 k^2이 된다.

여기서 움직일 거리에서 가장 큰 k를 찾은 후에 남은 거리는 k k-1.. 1 만큼씩 남은 거리가 0이 될 때까지 최대한 큼직큼직하게 움직이면 된다.

코드

#include <cstdio>

using ll = long long;

void solve() {
    int a, b; scanf("%d %d", &a, &b);
    int d = b - a;
    int k, ret;
    for (k = 0; ll(k + 1) * (k + 1) <= (1LL << 32); k++) {
        if (ll(k + 1) * (k + 1) > d) break; 
    }
    ret = 2 * k - 1;
    d -= k * k;
    for (int i = k; i >= 1; i--) {
        while (d >= i) {
            d -= i;
            ret++;
        }
    }
    printf("%d\n", ret);
}
int main() {
    int t; scanf("%d", &t);
    while (t--) solve();
}