BOJ 3671, 산업 스파이의 편지
ProblemSolving ·이 문제는 에라토스테네스의 체와 재귀함수를 이용한 문제입니다.
풀이
처음에는 int형으로만 순열을 구해보았지만 0이 포함된 수의 소수의 갯수를 구하지 못하여 문자열을 이용해야겠다고 생각했습니다.
소수를 판별하고 문자열을 이용한 순열만 잘해주신다면 어려움은 없습니다. 저는 실수로 답을 세주는 부분에 return을 넣어 한참 헤맸네요.
문자열을 이용하는 것이 까다로워 연습을 자주 해주면 좋을 것 같습니다.
#include<stdio.h>
#include<cmath>
#include<cstring>
#include<string>
#include<iostream>
using namespace std;
int arr[10000000],chk[10000000],ans,t,ichk[8];
string str;
void go(int depth, string s)
{
int now = stoi(s);
if (depth > str.size())
return;
if (arr[now] == 1 && chk[now] == 0)
ans++;
chk[now] = 1;
for (int k = 0; k < str.size(); k++)
{
if (ichk[k] == 0)
{
ichk[k] = 1;
go(depth + 1, s + str[k]);
ichk[k] = 0;
}
}
}
int main() {
for (int i = 2; i <= 9999999; i++)
arr[i] = 1;
for (int i = 2; i*i <= 9999999; i++)
for (int j = i * i; j <= 9999999; j += i)
arr[j] = 0;
scanf("%d", &t);
while (t--)
{
cin >> str;
ans = 0;
memset(chk, 0, sizeof(chk));
memset(ichk, 0, sizeof(ichk));
string s = "";
for (int i = 0; i < str.size(); i++)
{
ichk[i] = 1;
go(1, s + str[i]);
ichk[i] = 0;
}
printf("%d\n", ans);
}
return 0;
}