[BOJ/2023] 신기한 소수, c++

🔗 링크

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

2023번: 신기한 소수

https://github.com/jokj624/PS/blob/master/1000-5000/2023.cpp

jokj624/PS

🤯 한줄 후기

한줄 후기 : 그래프 분류 안봤으면 풀었을까 ?

🤷 문제

👩‍💻 풀이

한마디로 소수 옆에 소수 옆에 소수 이런식으로 붙이면 된다. 

dfs 탐색을 통해 가능하다. 

한자리 소수가 5개 (1,3,5,7,9) 밖에 없으니 1,3,5,7,9 다섯개를 N자리가 될 때까지 dfs 를 통해 붙이면 된다.

붙일 때 마다 소수 판별을 통해 해당 수가 소수인지 판별하여 소수일 때만 붙인다.

💻 코드

//AC
//BOJ 2023 신기한 소수
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
int pr[5] = {1, 3, 5, 7, 9};
int prime(int num){
	if(num == 1)	return 0;
	else if(num == 2)	return 1;
	for(int i=2; i<=sqrt(num); i++){
		if(!(num % i))	return 0;
	}
	return 1;
}
void dfs(int x, int N){
	if(N==1){
		printf("%d\n", x);
		return;
	}
	for(int i=0; i<5; i++){
		int next = x * 10 + pr[i];
		if(prime(next)){
			dfs(next, N-1);
		}
	}
}
int main(){
	int N;
	cin >> N;
	dfs(2, N);
	dfs(3, N);
	dfs(5, N);
	dfs(7, N);
	return 0;
}