BOJ) 신기한 소수

신기한 소수

2023번: 신기한 소수

풀이

 

처음에는 모든 숫자에 대해 DFS를 진행하면서 답을 구하려고 시도했다.

하지만 문제의 최대 조건인 n=8인 경우에 엄청난 시간이 소요되면서, 가지치기가 더 필요한 것을 느꼈다.

문제의 조건을 자세히 봤다.

 

n=4 인 경우에 나오는 수를 살펴보면, 첫번째 자리에는 {2,3,5,7} 만 오고 나머지 자리에는 {1,3,7,9}만 나와있음을 확인했다.

이 말은, n=3인 경우, n=2인 경우에도 앞의 자리가 위의 네가지 숫자 말고는 올 수 없음을 의미한다. (문제 조건이 숫자의 첫번째 자리, 1~2 자리, 1~3 자리 ... 1~n 자리까지 모두 소수여야 하기 때문에)

또한, n=5인 경우 ~ n=8인 경우에도 모두 저 숫자 범위 안에서 나온다는 뜻이다. (문제 조건에 따라서 n=5인 경우 1~4자리가 위의 경우만 남기 때문에)

 

그래서, 첫번째 자리에 올 수 있는 숫자와, 그 다음에 올 수 있는 자리의 숫자를 final로 미리 선언했다.

그리고 dfs에서 위의 숫자들을 가지고 n자리 까지 조합을 통해 경우의 수를 만들어 주었다.

 

dfs가 진행되면서, 중간중간에 현재까지 만들어진 숫자가 소수인지 판별하여 n까지 return되지 않은 숫자들을 답에 저장해줬다.

StringBuffer에 append와 delete를 직접 해주는 것은 좋지 않지만, n이 최대 8이기 때문에 불러오는 횟수가 많지 않을거라 판단해서 StringBuffer에 붙이고 빼주는 메소드를 직접 썼다. LinkedList나 ArrayList에 담아서 문자열로 만들거나 숫자로 바로 만드는 것이 더 비효율적이라고 판단했다.

 

 

코드

 

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

public class Main {
    final static String NEWLINE = "\n";
    final static int[] firstPrime = {2,3,5,7}, nextPrime = {1,3,7,9};
    final static int STANDARD = 10;
    static StringBuffer sb;
    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = br.read()-48;
        br.close();
        solution();
    }

    private static void solution() {
        sb = new StringBuffer();
        makePrimeNum(0, new StringBuffer());
        System.out.println(sb.toString());
    }

    private static void makePrimeNum(int cnt, StringBuffer listBuffer) {
        if(cnt >0 && listBuffer.length() >0) {
            if(!isPrime(listBuffer.toString())) { return; }
        }
        if(cnt == n) {
            if(listBuffer.length() == n) { sb.append(listBuffer.toString()).append(NEWLINE); }
            return;
        }
        if(cnt ==0) {
            for(int num : firstPrime) {
                listBuffer.append(num);
                makePrimeNum(cnt+1, listBuffer);
                listBuffer.deleteCharAt(listBuffer.length()-1);
            }
        } else {
            for(int num : nextPrime) {
                listBuffer.append(num);
                makePrimeNum(cnt+1, listBuffer);
                listBuffer.deleteCharAt(listBuffer.length()-1);
            }
        }
    }

    private static boolean isPrime(String numStr) {
        int num = Integer.parseInt(numStr);
        while(num /STANDARD !=0) {
            if(!isAnswer(num)) { return false ;}
            num /= STANDARD;
        }
        return true;
    }

    private static boolean isAnswer(int num) {
        for(int i=2; i*i<=num; i++) {
            if(num %i ==0) { return false; }
        }
        return true;
    }
}