[백준] 2023번 - 신기한 소수 (Java)(△)

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

2023번: 신기한 소수

 

<문제 해석>

1. 신기한 소수란? 왼쪽부터 1자리, 2자리.... N자리까지 모두 소수인 수

예) 7331 : 7 - 73 - 733 - 7331 모두 소수이다.

2. N자리가 주어졌을 때 신기한 소수를 모두 찾아서 출력하자.

3. 입력범위가 N : 1 ~ 8이다. DFS 백트래킹으로 풀이가 가능하다.

 

* 재귀함수 구현

1. 중복숫자 허용함(방문배열 사용X)

2. 순서다르면 다른 조합으로 인정 (i=1로 시작)

3. 가지치기를 활용해 시간복잡도를 줄인다.

  - 짝수는 스킵한다.

 

 

* 소수 판별 함수

// 소수 구하는 함수
// 1과 자신으로 밖에 안 나눠지는 수
boolean isPrime(int num) {
    for (int i=2; i<=num/2; i++) {
        if (num%i == 0) 
            return false;
    }
    return true;
}

 

<코드>

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

public class Main {
    static int N;
    static int A[];
    static StringBuilder sb = new StringBuilder();

    void DFS(int number, int level) {
        // 종료조건
        if (level == N) {
            if (isPrime(number)) {
                sb.append(number).append('\n');
            }
            return;
        }

        // 재귀호출
        for (int i=1; i<=9; i++) {
            // 가지치기 : 짝수는 스킵
            if (i%2 == 0) continue;

            // 소수이면 자리수를 하나 늘린다
            if (isPrime(number*10+i)) {
                DFS(number*10+i, level+1);
            }
        }
    }

    // 소수 구하는 함수
    // 1과 자신으로 밖에 안 나눠지는 수
    boolean isPrime(int num) {
        for (int i=2; i<=num/2; i++) {
            if (num%i == 0) 
                return false;
        }
        return true;
    }

	void Solve() {
        A = new int[N+1];
        // 첫 자리수가 소수인 경우만 백트래킹 전개한다.
        for (int i=2; i<=9; i++) {
            if (isPrime(i)) {
                DFS(i, 1);
            }
        }
        System.out.println(sb.toString());
	}

    void inputData() throws Exception {
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
    }

    public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.inputData(); // 입력 받는 부분
        m.Solve();// 여기서부터 작성
    }
}