[백준] 2023번 신기한 소수 찾기 - JAVA [자바] 설명 및 코드

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

 

2023번: 신기한 소수

 

문제

 

🐻‍❄️ 정답 코드 (이해가 안되시는 부분이 있다면, 아래의 상세 설명을 참고해주세요)

package SW역량테스트_A형준비;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * 7331
 * 7도 소수
 * 73도 소수
 * 733도 소수
 * 7331도 소수
 * => 왼쪽부터 1, 2, 3, 4 자리 모두 소수 : 신기한 소수
 *
 * N자리 소수 중 신기한 소수를 모두 찾아보자
 * 앞 자리에 올 수 있는 수 : 2 3 5 7
 * 두번째 자리 올 수 있는 수 ~ N번째 차례대로 구해보자
 * 어떻게 구할까?
 *
 * 문제 풀이 방식
 * 이문제는 DFS로 풀면 편하다.
 * 2 3 5 7로 시작
 * 첫자리 * 10 + 1,3,5,7,9 중 숫자 하나 => isPrime검사 => 소수라면 게속 들어가기
 */

public class Main_BJ_2023_신기한소수 {
    static int N;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        dfs(2, 1);
        dfs(3, 1);
        dfs(5, 1);
        dfs(7, 1);

        System.out.println(sb); // 출력
    }

    private static void dfs(int origin, int depth) {
        if (depth == N) { // 기저 조건
            sb.append(origin).append('\n'); // 스트링빌더에 추가
            return;
        }

        int[] odds = {1, 3, 5, 7, 9};
        int num = origin * 10;
        for (int i = 0; i < 5; i++) {
            if (isPrime(num + odds[i])) {
                dfs(num + odds[i], depth + 1);
            }
        }
    }

    private static boolean isPrime(int n) {
        for (int i = 2; i <= n/2; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }


}

---

🐯 풀이 방법 (DFS)

전 이 문제를 처음 풀었을 때, 1부터 N자릿수까지 돌면서 소수가 아닌 수를 걸러주는 방식으로 풀었는데요,

DFS로 다시 풀어보니 훨씬 깔끔하고 간단하게 풀 수 있었습니다!

 

문제에 나온 신기한 소수를 정리해보면 아래와 같습니다.

7331
* 7도 소수
* 73도 소수
* 733도 소수
* 7331도 소수

 

예제에 나온 그대로, N의 자리 수가 있다면 맨 왼쪽의 숫자(7)부터 시작하여 점점 오른쪽에 숫자를 하나씩 붙여가면서

완성된 수가 소수인지 확인한다면 이 문제를 풀 수 있습니다.

 

그렇다면 왼쪽에서 첫번째 자리에 올 수 있는 수는 무엇이 있을까요?

2, 3, 5, 7 입니다. 1, 4, 6, 8, 9는 소수가 아니기 때문에 첫번째 자리에 올 수 없습니다.

 

첫번째 자리(2, 3, 5, 7)를 정했다면 dfs 함수를 각각 호출합니다.

dfs(2, 1);
dfs(3, 1);
dfs(5, 1);
dfs(7, 1);

왜냐면, dfs에서 2, 3, 5, 7에 각각 10씩 곱한 뒤 뒤에 1~9까지 1의 자리 숫자를 더해줄 거거든요.

다만, 이때 더하는 숫자가 짝수라면 어차피 소수가 아니게 되므로 1, 3, 5, 7, 9 중 하나를 더해줍니다.

그리고 더해서 얻은 십의 자리 수(21, 23, 25, 27, 29 등. .)가 소수인지 아닌지 판별해줍니다.

소수가 맞다면 다시 dfs를 호출하여 다음의 똑같은 작업을 맡겨버립니다. (재귀 호출)

 

 

private static void dfs(int origin, int depth) {
     if (depth == N) { // 기저 조건
         sb.append(origin).append('\n'); // 스트링빌더에 추가
         return;
     }

     int[] odds = {1, 3, 5, 7, 9};
     int num = origin * 10;
     for (int i = 0; i < 5; i++) {
         if (isPrime(num + odds[i])) {
             dfs(num + odds[i], depth + 1); // 매개변수로는 더해진 값을 넘김, 깊이도 1 추가
         }
     }
}

 

🐣 소수를 판별하는 함수

소수인지 판별하는 방법은 아래와 같습니다.

n/2까지의 범위만 판단해도 되고 범위를 더 줄이고 싶다면 Math.sqrt(n) 로 대체해도 됩니다.

소수는 나누어 떨어지는 수가 1과 자기 자신 뿐이기 때문에 2 부터 n/2 의 범위까지 숫자로 n을 나누었을 때

하나라도 나누어 떨어지는 경우가 생긴다면 소수가 아니라는 것입니다.

private static boolean isPrime(int n) {
    for (int i = 2; i <= n/2; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

 

 

---

오늘 설명한 내용 중 어려우시거나 수정할 부분이 있다면 언제든지 댓글 달아주세요!

감사합니다 :)

 

좋댓 꾸욱 눌러주세요~!