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

---

풀이

1. 예제 해석

7331은 정답중 하나이다.
맨 앞의 수 7부터 시작한다.
7도 소수고, 73도 소수고, 733도 소수고, 7331도 소수이다.
이런 소수를 찾아내는 것이 목표이다.

2. 문제 해결 방법

• 우선 한자리 수가 소수여야 한다.
  따라서 첫 시작은 2, 3, 5, 7 로 좁혀진다.
• 두자리수부터 일의자리수는 홀수여야 한다.
  따라서 두자리수 이후는 홀수만 판별하면 된다.

3. 슈도 코드

int n : 목표 자릿수
int digit : DFS 내에서 현재 자릿수
StringBuilder sb

DFS(2,1);
DFS(3,1);
DFS(5,1);
DFS(7,1);
sout(sb)

DFS(num, digit){
if(digit == n ){
    if(소수){
        sb.append
        return;
       }
 }
 for(i = 1,3,5,7,9){
     if(10*num+i = 소수){
        DFS(10*num+i , digit+1);
    }
 }

4. 소수 판별 메소드

소수는 약수가 1과 자기자신만 있는 수이다.
숫자 num에 대하여 for(i=2;i<(int)Math.squt(num);i++) 로 반복하면서 num%i가 0이 아니면 소수이다.

소수 판별은 자주 사용하기 때문에 알아두면 좋다.

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

 

---

Code

package DFS.no2023_신기한소수;

import java.util.Scanner;

public class No2023 {
    static int n;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        //한자리 수가 소수인 경우는 2,3,5,7 가 있다.
        DFS(2,1);
        DFS(3,1);
        DFS(5,1);
        DFS(7,1);

        System.out.println(sb);
    }
    static void DFS(int num, int digit){
        if(digit == n){
            if(isPrime(num)){
                sb.append(num).append("\n");
                return;
            }
        }
        for(int i=1;i<=9;i+=2){
            if(isPrime(num*10+i)){
                DFS(num*10+i,digit+1);
            }
        }
    }
    static boolean isPrime(int number){
        for(int i=2;i<=(int)Math.sqrt(number);i++){
            if(number%i == 0)return false;
        }
        return true;
    }
}