3671번

3671번 - 산업 스파이의 편지

일단 숫자가 최대 7자리 이기 때문에 재귀를 통해서 풀 수 있을 거라고 생각했다.

또한 소수를 구하는 방식은 에라토스테네스의 체보다 그냥 그때 마다 구해서 문제를 풀었다.

0을 처리하기가 귀찮아서 string 으로 수를 만든 후 stoi 함수를 써서 문제를 풀었다.

각자 선택할지 안할지도 정해야 하고, 또한 앞 뒤 순서도 정해야 하기 때문에 check 값을 통한 백트래킹과 for문을 이용해서 재귀를 구현했다.

근데 예외처리 할 부분이 많아서 여러번 손을 봐야했고.. 약간 시간이 오래 걸리는 것 같다

더 정확하고 깔끔한 풀이를 위한 다른 사람들 코드를 좀 답습해야겠다.

<정답 코드>

#include<iostream>
#include<string>
#include<string.h>
using namespace std;
bool check[7];
int ans = 0;
bool chk[10000000];
bool first;
bool checkPrime(int n)
{
    if (n == 0 || n == 1)
    {
        return false;
    }
    for (int i = 2; i*i <= n; i++)
    {
        if (n%i == 0)
        {
            return false;
        }
    }
 
    return true;
}
void go(string &s,int size,string sum)
{
    if (sum.size() == 0 && !first)
    {
        return;
    }
 
    first = false;
 
    if (size == 0)
    {
        int summ = stoi(sum);
        if (chk[summ])
        {
            return;
        }
 
        chk[summ] = true;
 
        if (checkPrime(summ))
        {
            ans +=1;
        }
 
        return;
    }
 
    for (int i = 0; i < s.size(); i++)
    {
        if (!check[i])
        {
            check[i] = true;
            go(s, size - 1, sum + s[i]);
            go(s, size - 1, sum);
            check[i] = false;
        }
 
    }
 
 
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    int n;
    cin >> n;
 
    while (n--)
    {
        ans = 0, first = true;
        memset(check, false, sizeof(check));
        memset(chk, false, sizeof(chk));
        string str;
        cin >> str;
        int size = str.size();
        go(str,size,"");
 
        cout << ans << "\n";
    }
 
    return 0;
}