13913번: 숨바꼭질 4 / DP (실패) BFS (성공)

접근방법

N에서 1까지는 -1 가는 동작밖에 할 수 없으므로 i <= N인 경우 dp[i] = N - i

그 다음 바텀업 방식으로 dp[1]부터 +1 과 *2를 채워나갔다.

문제점

무조건 +1, *2로 최적의 해를 구할 수 없다.

5에서 17를 갈 때 5 -> 10 -> 9 -> 18 -> 17

-1을 추가해야 하는 상황, 따라서 dp의 조건인 그리디를 만족하지 못한다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    // input
    int N, K; cin >> N >> K;

    int dp[100001];
    memset(dp, -1, sizeof(dp));
    for (int i{N}; i > 0; i--) {
        dp[i] = N - i;
    }
    for (int i{1}; i < 100001; i++) {
        if (i + 1 <= 100000) {
            if (dp[i + 1] == -1) dp[i + 1] = dp[i] + 1;
            else dp[i + 1] = min(dp[i + 1], dp[i] + 1);
        }
        if (i * 2 <= 100000) {
            if (dp[i * 2] == -1) dp[i * 2] = dp[i] + 1;
            else dp[i * 2] = min(dp[i * 2], dp[i] + 1);
        }
    }

    vector<int> ans;
    int tmp{K};
    for (int i = dp[K] - 1; i > 0; i--) {
        if (tmp - 1 >= 0 && dp[tmp - 1] == i) {
            ans.push_back(tmp - 1);
            tmp--;
        }
        else if (tmp + 1 <= 100000 && dp[tmp + 1] == i) {
            ans.push_back(tmp + 1);
            tmp++;
        }
        else {
            ans.push_back(tmp * 2);
            tmp *= 2;
        }
    }
    ans.push_back(N);

    // output
    for (int i{0}; i < 30; i++) {
        cout << dp[i] << " ";
    }
    cout << dp[K] << "\n";
    while (!ans.empty()) {
        cout << ans.back() << " "; ans.pop_back();
    }
}