[백준-12852] 1로 만들기 2

단순 BFS 를 사용하면 100만 + 300만 정도의 복잡도가 나오게 되어서 전혀 복잡도가 터질 일이 없다.

따라서 BFS 를 따라 로직만 잘 처리해주면 된다. 로직은 다음과 같다.

• 처음 입력된 수와 비어있는 문자열을 queue 에 넣는다.
• 이 후 queue 의 front 를 빼고 3가지 연산 각각을 할 수 잇는지 확인하고 연산이 가능하면 연산된 값을 다시 queue 에 넣고 해당 숫자를 더한 문자열또한 queue 에 넣는다.
• 위의 과정을 1이 나올 떄까지 반복한다.

생각보다 간단한 알고리즘이다.

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
#include <string>

using namespace std;
typedef pair<int, string> pii;
int check[2000001];


void split_str(string s, vector<string>& ans) {
    auto current = s.find(',');
    auto previous = 0;
    while (current != string::npos) {
        string substring = s.substr(previous, current - previous);
        if (substring != "")
            ans.push_back(substring);
        previous = current + 1;
        current = s.find(',', previous);
    }
    ans.push_back(s.substr(previous, current - previous));
    cout << ans.size() - 1 << endl;
    for (auto i : ans)
        cout << i << " ";
    return;
}
int main() {
    int n;
    cin >> n;

    queue<pii> q;
    q.push({ n,"" });

    int cx;
    string ct;
    vector<string> ans;
    ans.push_back(to_string(n));

    if (n == 1) {
        cout << 0 << endl;
        cout << 1;
        return 0;
    }

    while (!q.empty()) {
        cx = q.front().first;
        ct = q.front().second;
        q.pop();
        if (cx == 1) {
            split_str(ct, ans);
            break;
        }
        if (cx % 3 == 0 && check[cx / 3] == 0) {
            check[cx / 3] = 1;
            q.push({ cx / 3, ct + "," + to_string(cx / 3) });
        }
        if (cx % 2 == 0 && check[cx / 2] == 0) {
            check[cx / 2] = 1;
            q.push({ cx / 2, ct + "," + to_string(cx / 2) });
        }
        if (check[cx - 1] == 0) {
            q.push({ cx - 1 , ct + "," + to_string(cx - 1) });
        }
    }

    return 0;
}

 

https://www.acmicpc.net/problem/12852

12852번: 1로 만들기 2