백준 2023 [신기한 소수] - JAVA

문제

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

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Q2023 {
    
    static int N;
    //2,4,6,8은 짝수로 나누어지고 5는 5로 나누어짐. 따라서 1,3,7,9로 끝나는 숫자만 소수가 될 수 있다.
    static int arrEndNumber[] = {1, 3, 7, 9};   
    
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());  // 1<= N <= 8
        
        //앞 자리도 소수이기때문에 2,3,5,7만 가능하다.
        dfs(2, 1);
        dfs(3, 1);
        dfs(5, 1);
        dfs(7, 1);
    }

    private static void dfs(int number, int numberLength) {
        if(numberLength == N && validNumber(number)) {
            System.out.println(number);
        }
        
        if(numberLength > N) {
            return;
        }
        
        //1,3,7,9
        for(int nIdx = 0 ; nIdx < arrEndNumber.length ; nIdx++) {
            int nextNumber = number * 10 + arrEndNumber[nIdx];
            
            if(validNumber(number)) {
                dfs(nextNumber, numberLength + 1);
            }
            
        }
    }

    private static boolean validNumber(int validNumber) {
        
        for(int nNum = 2; nNum < validNumber ; nNum++) {
            if(validNumber % nNum == 0) {
                return false;
            }
        }
        return true;
    }
}

 

해설

1. 1 <= N <= 8 자리의 전체숫자를 소수인지 판단하게 된다면 메모리초과/시간초과를 경험할 것이다.
   그럼 어떻게 접근해야할것인가?
2. '7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수'라고 문제에서 힌트를 주고 있다.
   첫 번째 자릿수부터 소수여야 한다. 한 자리 소수는 무엇인가? [2, 3, 5, 7] 4개의 숫자만 첫 번째 자리가 된다.
   다른 숫자로 시작하는 경우는 전부 고려하지 않아도 되게 된다.
3. 이제 다음 숫자로는 1~9 사이의 숫자를 붙여서 판단하면 될까? 좀 더 필터링을 할 수는 없을까?
   짝수는 2로 나누어지기 때문에 판단할 필요도 없다. 따라서 1,3,5,7,9만 남게 될 것이다.
   좀 더 생각해 보자. 5로 끝나는 숫자는 전부 5로 나누어 떨어진다.
   결과적으로 자릿수가 두 자리 이상인 소수의 마지막숫자는 [1, 3, 7, 9]가 될 수 있다.
4. 정리하면 [2, 3, 5, 7]로 시작하는 숫자에 [1, 3, 7, 9]의 숫자를 붙여가면서 소수인지 판단하면 된다.