BOJ-3671 산업 스파이의 편지

필요한 지식

1. 완전탐색
2. 에라스토테네스의 채
3. SET

접근

• 종이 조각으로 만들수 있는 모든 수를 체크해 준다.
• 만든수가 소수라면 SET에 넣어준다.
• 소수 체크에는 에라스토테네스의 채를 사용했다.

코드(C++)

#include <bits/stdc++.h>

#define FIO ios_base::sync_with_stdio(false), cin.tie(),cout.tie();
using namespace std;
int t;
bool sosu[10000000], chk[8];
string s;
set<int> se;

void init() {
    sosu[0] = sosu[1] = true;
    for (int i = 2; i * i <= 10000000; i++) {
        if (sosu[i]) continue;
        for (int j = i + i; j <= 10000000; j += i) {
            sosu[j] = true;
        }
    }
}
void go(int idx,int res) {
    if (idx == s.length()) return;

    for (int i = 0; i < s.length(); i++) {
        if (chk[i]) continue;
        chk[i] = true;
        if (!sosu[res*10+s[i]-'0'])se.insert(res*10+s[i]-'0');
        go(idx + 1,res*10+s[i]-'0');
        chk[i] = false;
    }
    return;
}

int main() {
    FIO;
    init();
    cin >> t;
    while (t--) {
        memset(chk, 0, sizeof(chk));
        cin >> s;
        go(0,0);
        cout << se.size() << "\n";
        se.clear();
    }
    return 0;
}

결과