1로 만들기

BOJ 1로 만들기 1463

BFS!

[-] Collapse

#include<cstdio>
#include<queue>
int main(){
    int n, ans = 0; scanf("%d", &n);
    std::queue<int> mq; mq.push(n);
    while (true){
        bool check = false;
        int size = mq.size();
        for (int i = 0; i < size; i++){
            int k = mq.front(); mq.pop();
            if (k == 1) check = true;
            if (k % 3 == 0) mq.push(k / 3);
            if (k % 2 == 0) mq.push(k / 2);
            mq.push(k - 1);
        }
        if (check) break;
        ans++;
    }
    printf("%d", ans);
}