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

🔺 문제

2023번: 신기한 소수

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        N = Integer.parseInt(br.readLine());
 
        // 가지치기 : 2,3,5,7
        DFS(2, 1);
        DFS(3, 1);
        DFS(5, 1);
        DFS(7, 1);  
    }
 
    // DFS
    static void DFS(int num, int digit) {
        // 종료 조건 : 자릿수 == N일 때
        if(digit == N) {
            if(isPrime(num)) {
                System.out.println(num);
            }
            return;
        }
 
        for(int i = 1 ; i <= 9 ; i++) {
            // 짝수라면 탐색 중지
            if(i % 2 == 0)    continue;
            
            // 🔔 소수라면 재귀 함수로 자릿수 늘림 🔔
            if(isPrime(num * 10 + i)) {    
                DFS(num * 10 + i, digit + 1);   // 자릿수 1씩 늘리면서
            }
        }
    }
 
    // 소수 판별
    static boolean isPrime(int n) {
        for(int i = 2 ; i <= (int)Math.sqrt(n) ; i++) {
            if(n % i == 0) {
                return false;
            }
        }
        return true;
    }
}

✅ 해결 아이디어
✔ DFS
- 자릿수가 한 개인 소수부터 탐색 시작
- 가지치기 : a가 짝수인 경우는 제외
- 이어서 자릿수가 2개인 현재 수 * 10 + a 를 계산해 소수인지 판단 (isPrime)
- 이 수가 소수면, 재귀 함수로 자릿수 하나 늘림

 

4를 입력했을 때, 과정은 이렇게

23 → 233 → 2333 → 239 → ...

 

 

---

🔺 다른 풀이들

[BOJ] 백준 2023번 : 신기한 소수 자바 (JAVA) 1

 

 

- 2,3,5,7 가지치기 안 하고 dfs(0,0) 한 번으로 끝내버림

로그인

 

- bfs 사용하심

로그인

---

💬 느낀 점

오랜만에 보는 소수 찾기... boolean을 사용하자...

에라토스테네스의 체도....

 

 

1회독	2회독	3회독	4회독	5회독
V	6/15

---

(참고)

✔ 에라토스테네스의 체

[알고리즘] 에라토스테네스의 체(소수 구하는 알고리즘) 자바 구현