백준 2023 신기한 소수 (C++)

2023번: 신기한 소수

백트랙킹을 통해 소수를 찾는 문제이다. 이 문제에서 주의해야 할 점은 메모리이다. 처음에 에라토스테네스의 체를 이용해 8자리 까지의 소수를 미리 모두 구한 후 조건에 만족하는 소수를 찾아주는 방식으로 문제를 접근했더니 메모리 초과가 나왔었다. 메모리 제한이 4MB 이기 때문에 에라토스테네스의 체를 사용하면 안된다. 문제를 잘 생각해보면 처음 올 수 있는 수는 2,3,5,7 로 4가지 밖에 올 수 없다. 그 이후는 경우의 수가 많이 줄어들기 때문에 하나씩 숫자를 추가해가면서 그때 그때 소수인지 판별하는 방식으로 접근해도 시간 초과가 일어나지 않는다. 메모리 초과때문에 살짝 햇갈렸던 문제였다.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int N;
vector<string> v;
int first[4] = { 2,3,5,7 };

void dfs(string s) {
    if (s.size() == N) {
        v.push_back(s);
        return;
    }

    for (int i = 1; i <= 9; i++) {
        s.push_back(i + '0');

        bool tf = false;
        for (int j = 2; j * j <= stoi(s); j++) {
            if (stoi(s) % j == 0) {
                tf = true;
                break;
            }
        }
        if (!tf) {
            dfs(s);
        }

        s.pop_back();
    }
}

void solution() {
    for(int i=0;i<4;i++){
        string s = "";
        s.push_back(first[i] + '0');
        dfs(s);
    }

    for (auto elem : v) {
        cout << elem << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;

    solution();

    return 0;
}