2023번: 신기한 소수(11분)

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

구현 아이디어 4분 구현 7분

풀이

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <vector>

using namespace std;

// 최대 8자리 숫자. 각 자리에 0~9까지 입력 가능.
int check[8];

void DFS(int L, int e)
{
    if (L == e)
    {
        //for (int i = 0; i < e; ++i)
            //printf("%d ", check[i]);
        //printf("\n");
        // 소수 판별.
        int result = 0, mul = 10;
        for (int i = 0; i < e; ++i)
        {
            result = result * mul + check[i];

            // result 소수 판별.
            for (int j = 2; j * j <= result; ++j)
                if (result % j == 0) return;
        }

        printf("%d\n", result);
    }
    else
    {
        for (int i = 0; i <= 9; ++i)
        {
            if (L == 0 && (i == 0 || i == 1)) continue;
            check[L] = i;
            DFS(L + 1, e);
        }
    }
}

int main() {
    int N;
    scanf("%d", &N);

    DFS(0, N);

    return 0;
}