BOJ 1011. Fly me to the Alpha Centauri

Leesoft·2022년 11월 5일
0
post-thumbnail

문제 링크

우주선이 ii번째로 이동한 거리를 kik_{i}라고 했을 때, 수열의 첫째 항과 마지막 항이 1이고 ki+1=ki1k_{i+1} = k_{i} - 1 또는 kik_{i} 또는 ki+1k_{i} + 1가 되는 상황에서 최소 이동 횟수를 묻는 문제이다!

문제를 푸는 핵심 첫 번째는 바로 kik_{i}의 최댓값에 대해 생각하는 것이다. 수열 kik_{i}는 이웃하는 항과의 차이가 항상 00 또는 11이어야 하므로, 다음과 같은 특징이 성립한다.

kik_{i}의 최댓값이 nn이라면, 우주선은 적어도 1+2++n+(n1)+(n2)++1=n21 + 2 + \cdots + n + (n-1) + (n-2) + \cdots + 1 = n^2만큼의 거리를 이동했어야 한다!

따라서, 가능한 nn의 최댓값은 yx\sqrt{y - x} 의 정수 부분이 될 것이다.

한편, 위와 같이 우주선이 (2n1)(2n - 1)번의 움직임으로 n2n^2만큼의 거리를 이동하고 남은 거리 rr에 대해 생각해 보자. 만약 rnr \le n이라면, rr만큼의 이동을 수열 1,2,,n,n1,,11, 2, \cdots, n, n-1, \cdots, 1의 적당한 위치에 추가하면 된다! 이때 숫자 rr은 위의 수열에 항상 포함되어 있으므로, 그 옆자리가 '적당한 위치'가 될 것이다. 다음으로 n>rn > r이라면 nn만큼의 이동을 수열의 nn 옆에 추가하고 rrnn만큼 줄이면 된다.

남은 이동 거리 r=(yx)n2r = (y - x) - n^2에 대하여, rnr \le n인 경우 1번만 더 이동하면 되고, r<nr < n인 경우 rn\lfloor{\frac{r}{n}}\rfloor번만큼 이동하고 나서, 나머지가 00이 아니면 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;
}
profile
🧑‍💻 이제 막 시작한 빈 집 블로그...

0개의 댓글