<백준 17071> 숨바꼭질 5

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 동생은 항상 걷기만 한다. 동생은 항상 매 초마다 이동을 하며, 이동은 가속이 붙는다. 동생이 이동하는 거리는 이전에 이동한 거리보다 1을 더한 만큼 이동한다. 즉, 동생의 처음 위치는 K, 1초가 지난 후 위치는 K+1, 2초가 지난 후 위치는 K+1+2, 3초가 지난 후의 위치는 K+1+2+3이다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 동생을 찾는 위치는 정수 좌표이어야 하고, 수빈이가 0보다 작은 좌표로, 50만보다 큰 좌표로 이동하는 것은 불가능하다.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 수빈이가 동생을 찾을 수 없거나, 찾는 위치가 500,000을 넘는 경우에는 -1을 출력한다.

 

---

풀이

 앞의 숨바꼭질 문제들이 단순한 BFS 문제였다면, 이 문제는 살짝 꼬아놓은 문제다.

 수빈이가 X번째 칸에 Y번만에 이동했다고 가정해보자.

그렇다면 수빈이는 1칸 전진 후 1칸 후진할 수 있으니 Y번, Y + 2번, Y + 4번... 째에 X에 도착할 수 있다.

즉, 동생이 x번째 칸에 y번째 이동했을 때 도착했다면, y가 Y보다 크거나 같고, y와 Y가 모두 짝수이거나, 홀수일때 만날 수 있다는 결론이 나온다.

 이 점을 잘 생각해서 코드를 짜게 되면, 특정칸에 '홀수번째'에 도착하는 경우와 '짝수번째'에 도착하는 경우를 나눠, BFS 테이블을 2차원으로 만들어서 작성하면 된다. 이동하는 횟수는 홀 - 짝 - 홀 - 짝 순으로 늘어날 수밖에 없으니 이동 횟수를 같이 저장해 나머지 연산을 하거나, 인덱스를 같이 저장하는 방법으로 구현할 수 있을 것이다.

코드

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int MAX = 500000;
int bfs[MAX + 1][2];
int N, K, add = 0, ans = MAX;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> N >> K;
    memset(bfs, -1, sizeof(bfs));
    bfs[N][0] = 0;

    queue<pair<int, int>> q;
    q.push({N, 0});

    while(!q.empty()) {
        pair<int, int> p = q.front(); q.pop();
        int x = p.first, y = p.second;

        if(x + 1 <= MAX && bfs[x + 1][(y + 1) % 2] == -1) {
            bfs[x + 1][(y + 1) % 2] = bfs[x][y] + 1;
            q.push({x + 1, (y + 1) % 2});
        } 
        if(x - 1 >= 0 && bfs[x - 1][(y + 1) % 2] == -1) {
            bfs[x - 1][(y + 1) % 2] = bfs[x][y] + 1;
            q.push({x - 1, (y + 1) % 2});
        }
        if(x * 2 <= MAX && bfs[x * 2][(y + 1) % 2] == -1) {
            bfs[x * 2][(y + 1) % 2] = bfs[x][y] + 1;
            q.push({x * 2, (y + 1) % 2});
        }
    }

    while(K <= MAX) {
        if(bfs[K][add % 2] <= add) {
            int tmp = max(bfs[K][add % 2], add);
            ans = min(ans, tmp);
        }
        add++;
        K += add;
    }

    if(ans == MAX) cout << -1;
    else cout << ans;
}