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

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

2023번: 신기한 소수

 

저는 해당 문제를 dfs를 이용해 문제 예시의 역순으로 각각의 숫자들이 소수인지를 판별하였습니다.

예를 들어 7331이라면 7이 소수인지 확인하고 73이 소수인지 ... 이렇게 왼쪽의 숫자부터 확인하였습니다. 

이유는 중복때문이였습니다. 오른쪽에서 처리하게된다면  7331에서 7이 소수인지 확인하고 7332에서도 확인하게 됩니다. 그래서 가장 높은 자리부터 소수라면 dfs의 depth를 들어가고 아니면 나오는 방법으로 문제를 해결하였습니다.

 

처음에는 보통의 문제 메모리라 지레 짐작하여 1억까지의 수를 boolean으로 담았었습니다. 당연하게 메모리 초과가 나게되면서 로직을 위와 같이 변경하였습니다.

 

package BOJ.ETC;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.function.Function;

public class BOJ_2023 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(br.readLine());
        int size = 1;
        for(int i = 0 ; i < n ; i++){
            size *= 10;
        }
        StringBuilder sb = new StringBuilder();
        dfs(0,0,n,sb);
        System.out.println(sb.toString());
    }
    private static void dfs(int num, int depth, int n, StringBuilder sb){
//        System.out.println(num);
        if(!checkPrim(num)){
            return ;
        }
        if(depth == n){
            sb.append(num+"\n");
            return ;
        }
        for(int i = 1 ; i < 10 ; i++){
            dfs(num * 10 + i,depth+1,n,sb);
        }
    }
    private static boolean checkPrim(int num){
        if(num == 0){
            return true;
        }else if(num == 1){
            return false;
        }
        for(int i = 2; i <= Math.sqrt(num) ; i++){
            if(num % i == 0){
                return false;
            }
        }
        return true;
    }
}