1011번: Fly me to the Alpha Centauri

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

1011번: Fly me to the Alpha Centauri

항상 정확한 거리만큼 공간 이동을 할 필요 없이, 같은 거리만큼 공간 이동을 두 번 할 때마다 공간 이동을 할 거리를 1 늘린다고 가정해 보자.

이해를 돕기 위해 점프한 거리를 막대의 높이로 시각화하면 위 이미지와 같다.

일부 특이한 경우가 아닌 이상, 이렇게 이동하다 보면 이동해야 할 거리를 초과하여 이동하게 된다. 그 직전에 공간 이동을 한 거리를 n, 실제로 목적지와의 거리를 k, 공간 이동을 한 횟수를 times라고 한다면 마지막으로 공간 이동을 한 거리는 그 직전에 이동한 거리 n, 혹은 이 거리에 1을 더한 n + 1이 된다. 그럼 이제 위 이미지의 막대를 아래와 같이 재배열해 보자.

빨간색 막대, 즉 마지막 공간 이동의 거리를 k로 조절하면 최적해를 찾을 수 있다

붉은 막대, 즉 목표 지점을 지나친 시점의 공간 이동을 제외하고 남은 막대를 공간 이동의 조건에 맞게 재배열한 뒤 붉은 막대, 즉 마지막에 공간 이동을 한 거리를 k로 조정하여 다시 조건에 맞게 끼워넣으면 위 그림과 같이 된다.

위 그림에서 시작점의 막대의 높이와 끝점의 막대의 높이가 각각 1이고, 이웃한 막대와의 높이 차가 1을 넘지 않으므로 위 그림은 문제의 조건을 만족한다. 또 위 그림에서 임의의 두 막대를 합치는 경우, 혹은 막대 하나를 쪼개어 여러 막대에 나누어 합치는 경우 문제의 조건을 위반하게 되므로 위 그림은 반드시 최적해가 된다. 따라서 구하고자 하는 답은 times가 된다.

#include <cstdio>

int test_case(int dist) {
    // 현재 공간 이동 이전에 jump만큼 공간 이동을 한 횟수
    bool flag = false;
    // times: 공간 이동을 한 횟수, jump: 공간 이동을 할 거리
    int times = 0, jump = 1;

    // 아직 목적지까지의 거리가 남아있을 때
    while (dist > 0) {
        // 거리 jump만큼 공간이동을 한 뒤
        dist -= jump;
        // 거리 jump만큼 공간 이동을 한 게 처음이라면 공간 이동 거리를 그대로 두고, 
        // 그렇지 않다면 공간 이동 거리를 1 늘린다
        jump += flag;
        // jump만큼 공간 이동을 했는지 여부를 갱신
        flag = !flag;
        // 공간 이동 횟수를 1 늘린다
        times++;
    }

    // 각 공간 이동을 적절히 재배치한 뒤 마지막 공간 이동의 거리를 적절히 재배치하면 최적해가 된다
    // 공간 이동을 한 횟수를 반환
    return times;
}

int main() {
    // T: 테스트 케이스의 수, x, y: 시작점과 끝점의 좌표
    int T, x, y;

    scanf("%d", &T);
    // 각 테스트 케이스마다
    while (T--) {
        // 시작점과 끝점을 입력받고 그 차만큼 이동할 때 걸리는 시간을 출력
        scanf("%d %d", &x, &y);
        printf("%d\n", test_case(y - x));
    }

    return 0;
}