[C++] 백준 2023: 신기한 소수

문제

[C++] 백준 2023: 신기한 소수 GOLD 5
https://www.acmicpc.net/problem/2023

 

---

 

접근 방법

이 문제는 N자리 소수를 찾는 문제이다.

 

완성된 N자리 수가 소수여야 할 뿐만 아니라, 앞에서부터 잘라 만든 모든 자리 수가 전부 소수여야 한다.

즉,
4자리 수라면 👉 1자리 → 2자리 → 3자리 → 4자리
모든 단계에서 소수 검사를 통과해야 한다.

그래서 단순히 N자리 수를 전부 만들고 검사하는 방식이 아니라,
자리수를 하나씩 늘려가며(DFS) 매 단계마다 소수인지 확인하고 진행하는 방식으로 풀었다.

 

• 1자리에서 시작 가능한 소수는 2, 3, 5, 7뿐이라 이 값들로 DFS를 시작한다.
• 다음 자리로 확장할 때는 짝수나 5로 끝나면 소수가 될 수 없으므로, 뒤에 붙일 숫자를 1, 3, 5, 7, 9로 제한한다.
• num에 한 자리씩 붙여 만든 t가 소수일 때만 다음 단계로 재귀 호출한다.
• 자리수가 N이 되면 그 수는 모든 단계에서 소수 검사를 통과한 것이므로 정답에 추가한다.

 

구현 시 주의할 점

• DFS로 숫자를 만들 때 매 단계에서 소수 검사를 통과한 경우에만 다음 자리로 내려가야 한다.
  (중간 단계에서 소수가 아니면 그 뒤에 뭘 붙여도 조건을 만족할 수 없음)
• 시작 숫자는 2, 3, 5, 7만 가능하다. (1자리 소수가 이 네 개뿐)
• jarisu == N일 때는 이미 직전 단계에서 소수 판정을 하고 들어온 값이므로 따로 소수 검사를 한 번 더 하지 않아도 된다.

 

---

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> ret;
int prime[5] = { 1,3,5,7,9 };
int N;

bool isPrime(int num)
{
	for (int i = 2; i < num; i++)
	{
		if (num % i == 0)
			return false;
	}
	return true;
}
void dfs(int num, int jarisu)
{
	if (jarisu == N)
	{
		ret.push_back(num);  //마지막에도 소수인지 검사해야되나??
		return;
	}
	for (int i = 0; i < 5; i++)
	{
		int t = num * 10 + prime[i];
		if (isPrime(t) == true)
			dfs(t, jarisu + 1);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	dfs(2, 1);  // N의 자리가 2,3,5,7
	dfs(3, 1);
	dfs(5, 1);
	dfs(7, 1);


	for (int i = 0; i < ret.size(); i++)
		cout << ret[i] << '\n';

	return 0;
}