[Java] 2023. 신기한 소수

문제

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다.

7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.

수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

출력

N자리 수 중에서 신기한 소수를 오름차순으로 정렬해서 한 줄에 하나씩 출력한다.

 

예제 입력 1

4

 

예제 출력 1

2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393

 

 

🦊 나의 풀이

import java.io.*;

public class Main{
    static int N;
    static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws Exception{
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(bf.readLine());
        dfs("", 0);
        bw.flush();

    }

    public static void dfs(String s, int depth) throws IOException{
        if(depth == N){
            bw.write(s+"\n");
            return;
        }

        for(int i=1; i<=9; i++){
            if(check(Integer.parseInt(s+Integer.toString(i)))) dfs(s+Integer.toString(i), depth+1);
        }
    }

    public static boolean check(int num){
        if(num == 1) return false;
        int end=(int)Math.sqrt(num);
        for(int i=2; i<=end; i++){
            if(num%i == 0) return false;
        }
        return true;
    }
}

다른 사람 풀이를 참고해서 구현

0부터 9가 아닌 1부터 9인 이유는 0이 들어가면 신기한 소수가 될 수 없어서다.

만약 1307이 있다면 130이 0때문에 소수가 안됨

 

 

// 실패
import java.io.*;
import java.util.*;

class Main {
    static int N;      // 자리 수
    static String num;
    static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(br.readLine());
        num=new String();
        dfs(0, 0);
        bw.flush();

    }

    public static boolean check(){
        int copied=Integer.parseInt(num);
        int end=copied/2;
        for(int i=2; i<=end; i++){
            if(copied%i != 0) return false;
        }
        return true;
    }

    public static void dfs(int start, int depth) throws IOException{
        if(depth == N){
            for(int i=0; i<N; i++){
                bw.write(num.charAt(i));
            }
            bw.write("\n");
        }

        for(int i=0; i<9; i++){
            if(i==0 && depth == 0) continue;
            num+=Integer.toString(i);
            if(check()) {
                dfs(i+1, depth+1);
            }else{
                return;
            }
        }
    }
}

check() 메소드의 반환값이 false면 그 전으로 돌아가야 하는데..

나는 돌아가지 않고 계속 추가할 수 있는 ㅠ.ㅠ

중복되지 않게 하는 것은 visited로 체크하면서 실행하면 되는데 이건 중복까지 고려해야하니 ㅠ

이 문제가 백트레킹인지 dfs인지 헷갈렸었다.

dfs는 모든 노드를 방문하고, 백트레킹은 정답이 될 수 없는 가지는 더이상 들어가지 않고 돌아간다.

21xx라는 수가 있으면 21이 소수가 아니므로 x가 무슨 수인지 상관없이 더이상 탐색하지 않는다.

결론은 dfs다.

 

 

🐕 다른 사람 풀이

// https://www.acmicpc.net/problem/2023
import java.io.*;

public class Main{
    public static int N;
    public static boolean f;
    public static StringBuilder sb=new StringBuilder();

    public static void main(String[] args) throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(br.readLine());
        dfs("", 0);
        System.out.println(sb.toString());
    }

    private static void dfs(String s, int cnt){
        if(cnt == N){
            sb.append(s+'\n');
            return;
        }
        for(int i=1; i<=9; i++){
            if(isPrime(Integer.parseInt(s+i))){
                dfs(s+i, cnt+1);
            }
        }
    }

    private static boolean isPrime(int num){
        if(num==1) return false;

        int sqrt=(int)Math.sqrt(num);
        for(int i=2; i<=sqrt; i++){
            if(num%i == 0) return false;
        }
        return true;
    }
}

아 문자열을 파라미터에 두면 되구나

isPrime 메소드 반환값이 false면 그 전으로 돌아갈 수 있다.

sqrt 메소드는 제곱근을 구할 때 쓴다.

어떤 수를 2에서 어떤 수의 제곱근까지 나눠보고, 나머지가 0이면 소수가 아니다.

 

 

문제 출처 👉 백준