BOJ 3671 - 산업 스파이의 편지 링크
(2023.05.22 기준 G4)

문제

숫자가 하나씩 적혀 있는 종이 조각이 많아야 7개가 주어진다. 모든 종이 조각을 사용하지 않아도 되고, 적절히 배치해서 소수가 되는 경우는 몇 개인지 출력

알고리즘

완탐 + 소수 판정

풀이

숫자는 최대 7개이므로 백트래킹 느낌으로 모든 숫자를 하나씩 만들어도 충분하다. 그러므로 모든 숫자를 일일이 소수인지 확인하면 된다.

그리고 만들어지는 수는 최대 9,999,999까지 나올 수 있다. 이는 에라토스테네스의 체를 사용하기에 충분한 수이므로 미리 소수인지 확인할 수 있는 배열을 만들어 놓자.

결과는 같은 숫자면 하나로 봐야 하기 때문에, set에 저장해서 저장된 수가 몇개인지 출력하면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

vector<bool> is_prime;
string numbers;
int n;
bool visited[7];
set<int> result;

// 에라토스테네스의 체
void sieve(int N){
    is_prime.resize(N);
    fill(is_prime.begin(), is_prime.end(), true);
    is_prime[0] = is_prime[1] = false;

    for (int i = 2, sqrt_N = sqrt(N); i <= sqrt_N; i++)
        if (is_prime[i])
            for (int j = i * i; j < N; j += i) is_prime[j] = false;
}

void dfs(int here, int level){
    // 현재 숫자가 소수이면 저장
    if (is_prime[here]) result.insert(here);

    // 현재 수가 숫자 n개를 모두 사용했다면 돌아가자.
    if (level == n) return;

    // 사용하지 않은 숫자를 찾아 붙였다가 다시 떼자.
    for (int i = 0; i < n; i++){
        if (visited[i]) continue;
        visited[i] = true;
        dfs(here * 10 + (int)(numbers[i] - '0'), level + 1);
        visited[i] = false;
    }
}

void solve(){
    cin >> numbers;

    n = numbers.size();
    fill(visited, visited + n, false);
    result.clear(); // 같은 숫자면 하나로 봐야 한다. 그러므로 set을 사용하자.
    dfs(0, 0);

    cout << result.size() << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    sieve(10000000);

    int c;
    cin >> c;
    while (c--) solve();
}

• Python

import sys; input = sys.stdin.readline

def dfs(here, level):
    # 현재 수가 소수이면 저장
    if is_prime[here]:
        result.add(here)

    # 현재 수가 숫자 n개를 모두 사용했다면 돌아가자.
    if level == n:
        return

    # 사용하지 않은 숫자를 찾아 붙였다가 다시 떼자.
    for i in range(n):
        if visited[i]:
            continue
        visited[i] = True
        dfs(here * 10 + numbers[i], level + 1)
        visited[i] = False

# 에라토스테네스의 체
is_prime = [True] * 10000000
is_prime[0] = is_prime[1] = False
for i in range(2, int(10000000 ** 0.5) + 1):
    if is_prime[i]:
        for j in range(i ** 2, 10000000, i):
            is_prime[j] = False


for _ in range(int(input())):
    numbers = list(map(int, input().strip()))

    n = len(numbers)
    visited = [False] * n
    result = set() # 같은 숫자면 하나로 봐야 한다. 그러므로 set을 사용하자.
    dfs(0, 0)

    print(len(result))