소수 판단 알고리즘과 함께 DFS 탐색 기법을 사용해야 해결할 수 있는 문제이다.
문제에서 숫자 자릿수 N이 주어졌을 때, 신기한 소수를 모두 찾아서 출력하라고 했으므로 먼저 소수를 판단하는 알고리즘이 필요하다.
P가 소수인지 판단하기 위해 사용하는 기본적인 알고리즘은 다음과 같다.
for i in 1 ~ P까지 진행:
if P % i == 0:
return False
return True근데 사실 조금만 더 찾아보면 P까지 반복하지 않고 제곱근인 까지만 반복해도 판단할 수 있다.
(왜 그런지 이유는 구글검색하면 나오니 찾아보길)
또한 2를 제외하고 소수는 모두 홀수이므로 이 역시 나머지셈을 진행할때 건너뛰어도 된다.
따라서 개선한 알고리즘은 다음과 같다.
if num < 2: return False
if num == 2: return True
if num % 2 == 0: return False
sqrt_num = sqrt(num)
for i in 3 ~ √P까지, 홀수만 반복:
if num % i == 0:
return False
return True이제 소수를 판단하는 알고리즘을 완성하였으니 DFS 탐색기법을 적용해야 한다.
만약 주어진 수의 길이가 N을 도달한 경우 그대로 출력하여 종료하면 되고, 길이 N을 도달하지 못한경우 주어진 수 * 10 + i를 통해 숫자의 오른쪽에 하나씩 붙여보며 소수인지 판별한 다음, DFS 탐색을 진행하면 된다.
Python
따라서 파이썬의 문제풀이 코드는 다음과 같다.
import sys, math
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N = int(input())
# 소수 판별 알고리즘
def isPrime(num):
if num < 2: return False
if num == 2: return True
if num % 2 == 0: return False
sqrt_num = int(math.sqrt(num))
# 입력된 값의 제곱근까지 나머지셈을 진행
for i in range(3, sqrt_num + 1, 2):
# 나누어 떨어지는 경우, 즉 약수를 찾은 경우
if num % i == 0:
return False # 가지치기 진행
return True # 소수이므로 DFS 탐색 진행
def DFS(num):
# 주어진 수의 길이가 N을 도달한 경우
if len(str(num)) == N:
print(num)
# 주어진 수 * 10 + i를 소수인지 판별해보면서
# DFS 탐색을 진행할지 가치지기를 진행할지 판단
else:
for i in range(1, 10, 2):
# 뒤에 홀수를 붙이면서 소수인지 판별하도록 실행
if isPrime(num * 10 + i):
DFS(num * 10 + i)
DFS(2)
DFS(3)
DFS(5)
DFS(7)Java
따라서 자바의 문제풀이 코드는 다음과 같다.
import java.util.Scanner;
public class Main {
static int N;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
DFS(2, 1);
DFS(3, 1);
DFS(5, 1);
DFS(7, 1);
}
static boolean isPrime(int num) {
if (num == 2) return true;
else if (num < 2) return false;
else if (num % 2 == 0) return false;
double sqrt_num = Math.sqrt(num);
for (int i = 3; i <= sqrt_num; i++) {
if (num % i == 0)
return false;
}
return true;
}
static void DFS(int num, int count) {
if (count == N) {
if (isPrime(num)) {
System.out.println(num);
}
return;
}
for (int i = 1; i < 10; i++) {
if (i % 2 == 0) continue;
if (isPrime(num * 10 + i)) {
DFS(num * 10 + i, count + 1);
}
}
}
}문제 설명에서 숫자를 하나씩 붙여보는 방식에 힌트를 얻고, DFS 탐색을 시작할 때 소수 중 한자리 수인 2, 3, 5, 7로 시작해야 한다는 점을 알아야 해결할 수 있다.
참고로 자바의 경우 자릿수를 검증하는 count 변수를 DFS의 매개변수에 따로 추가하였다.
주의해야할 점은 count 변수 증가 시 반드시 count + 1을 통해 값을 증가시켜야 한다는 점이다.
만약 ++count 나 count++을 진행할 경우 DFS 함수 특성 상 count 변수 스스로를 증가시켜 넘기기 때문에 최초의 4자리 수인 2333을 출력한 후 count 값이 5가 되는 문제가 생겨 제대로된 값을 출력하지 못한다.
아니면 count 대신 int length = String.valueOf(num).length();와 같이 num의 길이 자체를 읽어들여서 사용해야 한다.
