[백준] 2023 신기한 소수

문제링크 : www.acmicpc.net/problem/2023

2023번: 신기한 소수

처음에 문제를 보자마자 소수를 미리 구해두는 편이 편하다고 생각했지만 8자리까지 구하려고 하니 에라토스테네스의체로도 불가능할 것으로 생각했다. 메모리 제한은 4MB인 문제였다.

그래서 N자리인 수의 가장 큰 자리수부터 부분자리가 소수인 수들을 찾아갈 생각을 했다. 

1부터 9까지의 수들을 넣어보고 소수이면 다음자리에 들어갈 수 있는 수를 다시 넣는 방식을 N자리의 수가 될 때까지 탐색했다. dfs로 구현하면 자연스럽게 정렬된 순서가 됐다.

0은 가능한 경우가 없다.

import java.io.*;
import java.util.*;
public class Main {
	public static int N;
	public static ArrayList<Integer> ans = new ArrayList<Integer>();
	
	public static boolean isPrime(int k) {
	    if (k == 1) {
	        return false;
	    }
	 
	    int sqrt = (int) Math.sqrt(k);
	    for (int i = 2; i <= sqrt; i++) {
	        if (k % i == 0) {
	            return false;
	        }
	    }
	    return true;
	}
	
	public static void dfs(String sb, int idx){
		if(idx==N){
			ans.add(Integer.parseInt(sb));
		}
		for(int i=1;i<10;i++){ //중간에 0이 들어가면 안됨
			if(isPrime(Integer.parseInt(sb + i))){
				dfs(sb+i,idx+1);
			}
		}
	}
	
	public static void main(String[] args) throws Exception{
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		String sb = "";
		dfs(sb,0);
		for(int i=0;i<ans.size();i++){
			System.out.println(ans.get(i));
		}
	}

	
}