백준 2023 c++ "신기한 소수" -PlusUltraCode-

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

 

[필자 사고]

이 문제를 푸는 핵심 알고리즘은 DFS탐색을 이용하는거다.

 

또한 소수를 판별 하는 알고리즘도 알고 있어야 된다.

 

필자는 아르의 체 소수판별법을 이용하지 않았따. 그 이유는 불필요한 모든 소수를 구해야 되는 문제가 생겨 시간측면에서 손해를 보기 때문이다.

 

매번 숫자를 받을경우 하나하나 소수를 판별하는 알고리즘을 작성하였따.

 

DFS 의 구조를 설명하겠다.

1. 자릿수가 N과 같아지면 resultTank 에 넣는다.

2. nextNum이 소수 이면 DFS(nextNum) 을 실행한다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>

using namespace std;


bool isRealPrime(long num) {
	if (num <= 1)return false;
	for (int i = 2; i * i <= num; i++) {
		if (num % i == 0)return false;
	}
	return true;
}

int N;
vector<long> resultTank;


void DFS(long startNum) {
	string jarisu = to_string(startNum);
	if (jarisu.size() == N) {
		resultTank.push_back(startNum);
		return;
	}

	for (int i = 1; i < 10; i += 2) {
		long nextNum = startNum * 10 + i;
		if (isRealPrime(nextNum) == true) {
			DFS(nextNum);
		}
	}
}

void GameStart() {

	DFS(2);
	DFS(3);
	DFS(5);
	DFS(7);

	sort(resultTank.begin(), resultTank.end());
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> N;

	GameStart();
	for (int i = 0; i < resultTank.size(); i++) {
		cout << resultTank[i] << '\n';
	}
	
}