백준 3671번 산업 스파이의 편지 [C++]

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

 

 

#문제 간단 정리

 

소수판별 + 구현문제

 

#문제 해결 방법

 

우선 숫자가 주어지면 이 숫자로 만들수 있는 조합으로

만들수 있는 소수이니

 

숫자로 만드는조합 -> dfs 사용

 

소수판별 -> 에라토스테네스의 체 

 

이렇게 두가지 구현하면 된다

 

dfs구현에서 최대길이가 7자리수라 시간복잡도에는 문제 없는 것을 알 수 있다.

 

#전체 코드

#include <iostream>
#include <vector>
#include <string>
#include <set>
using namespace std;

static const int MAX = 10'000'000;
bool primeArr[MAX];    
set<int> primeSet;    

string s;
set<int> madeNumbers;   

void sieveOfEratosthenes() {
    primeArr[0] = false;
    primeArr[1] = false;

    for (int i = 2; i < MAX; i++) {
        primeArr[i] = true;
    }

    for (int i = 2; i * i < MAX; i++) {
        if (primeArr[i]) {
            for (int j = i * i; j < MAX; j += i) {
                primeArr[j] = false;
            }
        }
    }
}


void dfs(string& input, vector<bool>& used, int length) {

    if ((int)input.size() == length) {
  
        int num = stoi(input);
        madeNumbers.insert(num);
        return;
    }


    for (int i = 0; i < (int)s.size(); i++) {
        if (!used[i]) {
            used[i] = true;
            input.push_back(s[i]);

            dfs(input, used, length);

            input.pop_back();
            used[i] = false;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    sieveOfEratosthenes();


    int t;
    cin >> t;
    while (t--) {
        cin >> s;
        madeNumbers.clear();


        for (int len = 1; len <= (int)s.size(); len++) {
            vector<bool> used(s.size(), false);
            string tmp;
            dfs(tmp, used, len);
        }


        int Pcount = 0;
        for (int num : madeNumbers) {
            if (primeArr[num]) {
                Pcount++;
            }
        }

        cout << Pcount << "\n";
    }
    return 0;
}