题解 | #数的构造#

#include <bits/stdc++.h>

using namespace std;


int main() {
    int n;
    cin >> n;
    vector<int> d(n + 1);// d[i] : 到值为i所需最小的次数。
    queue<int> q;
    q.push(0);
    while (!q.empty()) {
        int c = q.front();
        q.pop();
        int nx = c + 1;
        if (c == n) break;

        if (d[nx] == 0) {
            d[nx] = d[c] + 1;
            q.push(nx);
        }

        nx = c * 3;
        if (nx > n) continue;
        if (d[nx] == 0) {
            d[nx] = d[c] + 1;
            q.push(nx);
        }
    }

    cout << d[n] << endl;
    return 0;
}