[백준 / Java] 2023: 신기한 소수 (백트래킹)

난이도: Gold 5

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

 

문제

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

7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.

수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

출력

N자리 수 중에서 신기한 소수를 오름차순으로 정렬해서 한 줄에 하나씩 출력한다.

예제 입력 1 복사

4

예제 출력 1 복사

2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393

---

 

데이터 수 N의 크기가 크지 않고, 출력된 수들를 보니까 뒷자리들만 여러번 바뀌다가 뒷자리가 모두 바꼈으면 앞자리들을 바꾸기 시작한다.

그러므로 이 문제는 틀림없이 백트래킹 알고리즘이다.

 

dfs 메서드의 매개변수로는 자릿수를 뜻하는 depth와, depth 자릿수의 소수를 뜻하는 prime을 선언한다.

그리고 1, 2, 3, ... N번째 자릿수가 모두 소수여야 하므로, 맨 앞자리도 당연히 소수여야 한다.

한 자리수중에 소수는 2, 3, 5, 7밖에 없다.

그러므로 맨 처음에 dfs의 prime 인수로는 2, 3, 5, 7을 넘겨주면 된다.

맨 앞(0번째)자리는 이미 정해졌으므로, 1번째 자리부터 찾기 위해 depth 인수는 1을 넘겨준다.

 

    // 신기한 소수의 맨 앞(0번째)자리는 무조건 2, 3, 5, 7로 시작

    dfs(1, 2);  // 1번째 자리에서 소수 2가 맨 앞에 오는 소수 찾으러 가기

    dfs(1, 3);  // 1번째 자리에서 소수 3이 맨 앞에 오는 소수 찾으러 가기

    dfs(1, 5);  // 1번째 자리에서 소수 5가 맨 앞에 오는 소수 찾으러 가기

    dfs(1, 7);  // 1번째 자리에서 소수 7가 맨 앞에 오는 소수 찾으러 가기

 

 

dfs 메서드는 다음과 같다.

 

    // depth번째 자리에서 소수 prime이 맨 앞에 오는 소수를 찾는 메서드

    public static void dfs(int depth, int prime) {

        // 현재 깊이 depth가 신기한 소수의 자릿수 N과 같다면

        // 현재 소수 prime은 N자리 신기한 소수

        if (depth == N) {

            magicPrimes.add(prime); // 신기한 소수 리스트에 현재 소수 prime 추가

            return;     // depth - 1번째 자리로 돌아가서 소수 찾으러 가기

        }

       

        // 1 ~ 9 홀수만 탐색 (짝수는 절대 소수가 될 수 없음)

        for (int i = 1; i <= 9; i += 2) {

            // 현재 소수 prime의 맨 뒤에 한자리 수의 홀수 i를 덧붙인 숫자 생성

            int n = prime * 10 + i;

            if (isPrime(n)) {   // n이 소수라면

                // depth + 1번째 자리에서 소수 n이 맨 앞에 오는 소수 찾으러 가기

                dfs(depth + 1, n);

            }

        }

    }

 

 

신기한 소수들을 담을 magicPrimes 리스트는 전역 변수로 선언했다.

2자리 이상부터 짝수는 절대 소수가 될 수 없으므로, 홀수만 탐색한다.

int n = prime * 10 + i;

이 코드는 prime 뒤에 한 자리 수의 홀수 i를 덧붙인 숫자를 생성하는 것이다.

예를 들어 매개변수로 받은 prime이 2이고, 현재 i가 3이라면,

int n = 2 * 10 + 1 = 23; 이 된다.

그리고 이 n이 소수이므로 dfs 인수로 n을 넘겨준다.

다음에 매개변수로 받은 prime은 23이고, 현재 i가 3이라면,

int n = 23 * 10 + 3 = 233; 이 된다.

그러므로 이 코드는 원래 숫자 뒤에 한자리 숫자들을 덧붙이는 완벽한 코드가 된다.

이렇게 탐색하다가 depth가 N이랑 같다면, N자리 소수(신기한 소수)를 구한 것이므로 리스트에 추가시킨다.

소수인지 판별하는 isPrime 메서드는 다음과 같다.

 

    // n이 소수인지 판단하는 메서드

    public static boolean isPrime(int n) {

        // n의 제곱근만큼만 탐색

        // => 소수가 아니라면 무조건 제곱근 이하의 수로 나누어 떨어지기 때문에 굳이 n까지 탐색할 필요 없음

        for (int i = 2; i <= Math.sqrt(n); i++) {

            // n이 2 이상 n의 제곱근 이하의 어떠한 수로 나누어 떨어진다면

            if (n % i == 0) {

                return false;   // 소수가 될 수 없음

            }

        }

        return true;    // n이 2 이상 n의 제곱근 이하의 어떠한 수로도 나누어 떨어지지 않는다면 소수

    }

 

 

그리고 마지막으로 신기한 소수들이 담긴 magicPrimes 리스트의 원소들을 차례대로 출력하면 된다.

 

전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
 
public class P2023_신기한소수 {
    static int N;    // 신기한 소수의 자릿수
    static List<Integer> magicPrimes = new ArrayList<>();    // 신기한 소수 리스트
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        
        // 신기한 소수의 맨 앞(0번째)자리는 무조건 2, 3, 5, 7로 시작
        dfs(1, 2);    // 1번째 자리에서 소수 2가 맨 앞에 오는 소수 찾으러 가기
        dfs(1, 3);    // 1번째 자리에서 소수 3이 맨 앞에 오는 소수 찾으러 가기
        dfs(1, 5);    // 1번째 자리에서 소수 5가 맨 앞에 오는 소수 찾으러 가기
        dfs(1, 7);    // 1번째 자리에서 소수 7가 맨 앞에 오는 소수 찾으러 가기
        
        // 신기한 소수 리스트에 담긴 신기한 소수를 차례대로 출력
        for (int magicPrime : magicPrimes) {
            bw.write(magicPrime + "\n");
        }
        
        bw.flush();
    }
    
    // depth번째 자리에서 소수 prime이 맨 앞에 오는 소수를 찾는 메서드
    public static void dfs(int depth, int prime) {
        // 현재 깊이 depth가 신기한 소수의 자릿수 N과 같다면 
        // 현재 소수 prime은 N자리 신기한 소수
        if (depth == N) {
            magicPrimes.add(prime);    // 신기한 소수 리스트에 현재 소수 prime 추가
            return;        // depth - 1번째 자리로 돌아가서 소수 찾으러 가기
        }
        
        // 1 ~ 9 홀수만 탐색 (짝수는 절대 소수가 될 수 없음)
        for (int i = 1; i <= 9; i += 2) {
            // 현재 소수 prime의 맨 뒤에 한자리 수의 홀수 i를 덧붙인 숫자 생성
            int n = prime * 10 + i;
            if (isPrime(n)) {    // n이 소수라면
                // depth + 1번째 자리에서 소수 n이 맨 앞에 오는 소수 찾으러 가기
                dfs(depth + 1, n);
            }
        }
    }
    
    // n이 소수인지 판단하는 메서드
    public static boolean isPrime(int n) {
        // n의 제곱근만큼만 탐색
        // => 소수가 아니라면 무조건 제곱근 이하의 수로 나누어 떨어지기 때문에 굳이 n까지 탐색할 필요 없음
        for (int i = 2; i <= Math.sqrt(n); i++) {
            // n이 2 이상 n의 제곱근 이하의 어떠한 수로 나누어 떨어진다면
            if (n % i == 0) {
                return false;    // 소수가 될 수 없음
            }
        }
        return true;    // n이 2 이상 n의 제곱근 이하의 어떠한 수로도 나누어 떨어지지 않는다면 소수
    }
}