순간을 기록으로

[Java] 신기한 소수 찾기_백준_2023 본문

Problem Solving

[Java] 신기한 소수 찾기_백준_2023

luminous13 2022. 10. 28. 17:42

문제

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

 

2023번: 신기한 소수

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

www.acmicpc.net

 

풀이

재귀를 이용한 DFS와 자릿수 개념을 활용하는 문제입니다.

N자리 신기한 소수를 모두 출력해야되는데요.

신기한 소수란 왼쪽부터 1자리, 2자리, ..., N자리까지의 수가 모두 소수인 수를 말합니다.

 

그렇다면 왼쪽부터 1자리 수부터 시작해서 N자리 수까지 소수인지 확인해서 모두 소수였을 때 출력해주면 될 것 같습니다.

1자리에서는 소수가 될 수 있는 숫자는 2, 3, 5, 7입니다.

하지만 2자리 부터는 일의 자리수의 숫자가 11처럼 1이 올 수도 있습니다. 즉 2, 3, 5, 7이 아닌 다른 수로도 소수를 만들 수 있습니다.

그래도 확실한 건 짝수가 오면 2로 나눌 수 있기 때문에 소수가 될 수 없으므로 홀수일 경우에만 소수가 될 가능성이 있습니다.

 

마지막으로 출력할 때에는 오름차순으로 출력을 해야되는데 탐색방향을 숫자가 커지는 방향으로 탐색하기 때문에 따르 정렬을 할 필요는 없습니다.

소스코드

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
50
51
52
53
package 백준;
 
import java.util.Scanner;
 
/*
* N자리 수 중에서 신기한 소수를 오름차순으로 정렬해서 한 줄에 하나씩 출력해라.
* 신기한 수란 왼쪽부터 1자리, 2자리, ..., N자리 수 모두 소수인 수를 의미한다.
*
* dfs을 이용하여 숫자를 오른쪽에 붙여나가다가 N자리 수가되면 출력
*
* */
public class 신기한소수_2023 {
    static int N;
    static StringBuilder sb = new StringBuilder();
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
 
        dfs("2");
        dfs("3");
        dfs("5");
        dfs("7");
 
        System.out.println(sb);
    }
 
    public static void dfs(String num) {
        if (!isPrime(Integer.parseInt(num)))
            return;
 
        if (num.length() == N) {
            if (isPrime(Integer.parseInt(num)))
                sb.append(num).append("\n");
        } else {
            for (int i=1; i<=9; i+=2) {
                dfs(num + i);
            }
        }
    }
 
    public static boolean isPrime(int num) {
        if (num <= 1return false;
 
        for (int i=2; i<=(int)Math.sqrt(num); i++) {
            if (num%i == 0)
                return false;
        }
 
        return true;
    }
}
 
cs

 

 

 

'Problem Solving' 카테고리의 다른 글

[LeetCode] Swap Salary  (0) 2022.11.06
[LeetCode] Calculate Special Bonus  (0) 2022.11.06
[Java] 백준_ABCDE_13023  (0) 2022.08.19
[Java] 백준_신기한 소수_2023  (0) 2022.08.17
[Java] 백준_연결 요소의 개수_11724  (0) 2022.08.17
Comments