백준 2023번(신기한 소수)[JAVA]

풀이

자릿수를 n까지 하나씩 늘려가며 모든 소수를 찾는 완전 탐색 문제이다. 즉, dfs를 활용하여 풀 수 있다. dfs에 입력한 수가 소수라면, 입력한 수에 * 10을 하여 자릿수를 늘리고, 그 뒤에 for문을 통해 수를 이어붙힌 후, 소수인지 판별한다. 그리고 그 수가 소수일 경우, 그 수를 다시 dfs에 입력한다. 자릿수가 늘어났으므로, 자릿수도 +1해서 입력한다.
시간 복잡도를 줄이는 방법은 아래와 같다.

1. 문제를 보면 알 수 있듯이, 출력되는 수의 첫번째 값은 무조건 소수여야한다. 그래야 그 뒤에 숫자를 붙여가면서 문제를 풀 수 있다.즉, 시작은 1~9까지 모두 찾아보는 것이 아니라 2,3,5,7만 찾아봐도 된다.
2. 붙여가는 수들이 짝수이면 소수가 아니게 되므로, 뒤에 이어붙이는 수들은 홀수인 1,3,5,7,9여야 한다.

소스 코드

import java.util.*;

public class 신기한소수 {
	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 k) {
		for (int i = 2; i <= k/2; i++) {
			if (k%i == 0)
				return false;
		}
		return true;
	}
	
	static void dfs(int start, int k) {
		if (k == n) {
			if (isPrime(start)) {
				System.out.println(start);
			}
			return;
		}
		
		for (int i = 1; i < 10; i++) {
			if (i % 2 == 0)
				continue;
			
			if (isPrime(start*10+i)) {
				dfs(start*10+i, k+1);
			}
		}
	}
}

태클 감사합니다.
조언 환영입니다.