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

코테/백준

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

imname1am 2023. 4. 17. 12:25

🔺 문제

2023번: 신기한 소수

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

www.acmicpc.net

🔺 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

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;
    }
}
Colored by Color Scripter

cs

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