문제

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

설명

N의 최대값이 8이므로 시간 복잡도를 거의 고려하지 않아도 된다.
주인장은 깊이 우선 탐색(DFS)과 소수 구하는 공식을 이용해서 위 문제를 해결하려한다.

깊이 우선 탐색

깊이 우선 탐색(DFS, Depth-First Search)알고리즘은 그래프의 시작 노드에서 출발하여 탐색할 한쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.

📖읽어보기 - https://velog.io/@cod0216/알고리즘깊은-우선-탐색DFS

소수

정수 A의 약수 a와 b가 있다고 할 때 a와 b값이 똑같다면 a와 b는 루트 A 곱하기 루트 A로 표현 할 수 있다 이를 막대 그래프로 표현하면 다음과 같다.

여기서 A의 약수 하나인 a가 가 루트A보다 크게되면 자연스럽게 A의 약수 b는 루트 A보다 작아지게 된다.

이 점을 이용해서 다음과 같은 식을 만들 수 있다.

📖읽어보기 - https://velog.io/@cod0216/알고리즘에라토스테네스의-체정수론

풀이

이 문제는 각 자리 수가 증가하면서 모두 소수인 수를 찾는 문제이다.
처음 일의 자리에서 소수를 찾고 찾은 소수가 2의 자리가 될때 소수를 찾고 다시 3의자리 N의 자리까지 소수가 되는 수를 찾으면 된다.

먼저 소수를 찾는 함수를 만든다.
값이 넘어 오면 해당 값이 소수인지 아닌지를 판별하면 된다.

넘어온 값이 i값으로 나누었을때 0이 있다면 그 값은 약수가 존재하므로 소수가 아니게 된다. 반대로 넘어온 값이 소수 맞다면 true를 리턴해주면 된다.

이후 깊이 우선 탐색, DFS 함수를 만들어 주면 된다.

먼저 일의 자리가 소수인지를 판별한 후 해당 숫자를 가지고 십의 자리(소수*10)로 옮겨준후 0~9까지 일의 자리에 더해주며(=소수*10+0~9) 소수를 판별한다. 이후 판별된 소수만을 가지고 N자리까지 이 과정을 반복(DFS)하면 된다.

💡 소수
일의 자리에서 소수는 2, 3, 5, 7이다. 이걸 이용해서 main코드를 짤때 DFS(2, 자리수), DFS(3, 자리수), DFS(5, 자리수), DFS(7, 자리수)로 미리 넣어주면 불필요한 연산을 줄일 수 있다 이후 십의 자리부터는 num*10 + 1, num*10+3, num*10+7, num*10+9로 불필요한 연산을 줄일 수 있다.

코드

import java.util.*;

public class J2023 {
    static int count;
    public static void main(String[] args){
     Scanner scanner = new Scanner(System.in);

     int n = scanner.nextInt();
     count = n;

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

    }
    public static void DFS(int num, int cnt){
     //만약 소수라면
         if(cnt == count) {
             System.out.println(num);
             return;
         }
         cnt +=1;
        for(int i = 0; i < 10; i++) {
            int value = num * 10 + i;
                if (isPrime(value))
                    DFS(value, cnt);

        }

    }
    public static boolean isPrime(int num){
        for(int i = 2; i<=Math.sqrt(num); i++){
            if(num % i == 0)
                return false;
        }
        return true;

    }
}