문제

문제 링크

해설

• 이 문제는 다른 포스트에서 이미 다룬 적이 있기 때문에 해당 포스트 주소를 올리는 것으로 대체하겠습니다.

코드

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

int N, K;
int visited[100'001];

void get_trace(int here, int there) {
    if (here != there) get_trace(here, visited[there]);
    cout << there << ' ';
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    cin >> N >> K;

    if (N > K) {    // 거꾸로 가는 방법은 1가지 밖에 없습니다.
        cout << N - K << '\n';
        for (int i = N; i >= K; i--) cout << i << ' ';
        return 0;
    }

    int answer_time = 1e9;

    queue<pair<int, int>> q;
    q.emplace(N, 0);
    // 인덱스 '0'번이 유효한 번호기 때문에 -1로 초기화해야 합니다!
    memset(visited, -1, sizeof(visited));
    visited[N] = N;
    while (!q.empty()) {
        int here = q.front().first, now = q.front().second;
        q.pop();
        if (now > answer_time) continue;
        if (here == K) { answer_time = now; break; }
        for (int there : {here * 2, here + 1, here - 1}) {
            if (0 <= there && there <= 100'000 && visited[there] == -1) {
                q.emplace(there, now + 1);
                visited[there] = here;
            }
        }
    }
    cout << answer_time << '\n';
    get_trace(N, K);

    return 0;
}

소스코드 링크

결과