[BaekJoon] 2023 신기한 소수 (Java)

1.  문제 링크

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

2.  문제

요약

• N자리의 숫자 중 왼쪽부터 1자리, 2자리, 3자리, 4자리, ... N자리 수 모두 소수인 수를 신기한 소수라고 합니다.
• N이 주어졌을 때, N자리 신기한 소수를 모두 찾는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 8보다 작거나 같은 N이 주어집니다.
• 출력: N자리 수 중 신기한 소수를 오름차순으로 정렬해서 한 줄에 하나씩 출력합니다.

3.  소스코드

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

public class Main {
	static String[] first_primes = {"2", "3", "5", "7"};
	String[] other_values = {"1", "3", "7", "9"};
	static int n;
	public boolean isPrime(int num) {
		for(int i = 2; i <= Math.sqrt(num); i++) {
			if(num % i == 0)
				return false;
		}
		return true;
	}
	
	public void getPrimes(String num, int count) {
		if(count >= n) {
			System.out.println(num);
			return;
		}
		for(int i = 0; i < other_values.length; i++) {
			String next_num_str = num + other_values[i];
			int next_num = Integer.parseInt(next_num_str);
			if(isPrime(next_num)) {
				getPrimes(next_num_str, count + 1);
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		br.close();
		Main m = new Main();
		for(int i = 0; i < first_primes.length; i++) {
			m.getPrimes(first_primes[i], 1);
		}
	}
}

4.  접근

• 해당 문제는 백트래킹을 이용하여 해결할 수 있습니다.
• 왼쪽 1자리 수가 소수여야 하므로 왼쪽 1자리에 들어갈 수 있는 수는 소수인 2, 3, 5, 7만 가능합니다.
• 왼쪽부터 2자리, 3자리, ..., N자리 모두 소수여야 하는데 끝자리 수가 0, 2, 4, 5, 6, 8이라면 2 또는 5 등으로 나누어 떨어질 수 있으므로 끝자리 수는 1, 3, 7, 9만 가능합니다.
• 이를 이용하여 첫 자리는 2, 3, 5, 7 중 하나이며 나머지 자리는 1, 3, 7, 9 중 하나인 수들을 찾습니다.
• 첫 번째 자리 수를 첫 번째 자리 수에 올 수 있는 첫 번째 수인 2부터 시작해서 수들을 찾고 이후 숫자는 나머지 자리에 올 수 있는 수 중 첫 번째 수인 1부터 시작하여 채워나갑니다.
• 왼쪽부터 한 자리씩 채워나가면서 해당 수가 소수인지 확인하고 그렇지 않다면 다음 숫자로 채우고 해당 수 역시 소수인지 확인합니다.
• 위 방식으로 N자리 수가 완성될 때까지 한 자리씩 채운 수가 소수인지 확인하고 완성된 N자리 수 역시 소수라면 해당 수를 출력합니다.
• N자리 수가 완성됐다면 이전으로 돌아가 나머지 자리에 가능한 수 중 다음 수를 이용하여 N자리 수를 만들고 소수인지 확인합니다.
• 이러한 방식을 이용해 가능한 모든 수들을 만들어보고 그 수들 중에서 N자리의 신기한 소수인 수들만 출력합니다.

1. 첫 번째 자리에 들어갈 수 있는 수들인 2, 3, 5, 7을 배열 first_primes에 넣어주고 나머지 자리에 들어갈 수 있는 수들인 1, 3, 7, 9를 배열 other_values에 넣어줍니다.
2. first_primes의 첫 번째 수부터 마지막 수까지 반복문을 돌며 해당 수를 첫 번째 자리에 배치시키면서 N자리의 신기한 소수를 구합니다.
   1. 만약 만들어진 수가 N자리라면 해당 수를 출력합니다.
   2. 그렇지 않다면 other_values의 첫 번째 수부터 마지막 수까지 반복문을 돌며 수를 만듭니다.
      1. 현재까지 만들어진 수에 현재 반복문에 해당하는 수를 추가합니다.
      2. 만들어진 수가 소수인지 확인합니다.
         • 만들어진 수를 2부터 만들어진 수의 제곱근까지로 각각 나눠보면서 나누어떨어지는 수가 있다면 소수가 아니므로 false를 반환하고 모두 나누어떨어지지 않는다면 해당 수는 소수이므로 true를 반환합니다.
      3. 만들어진 수가 소수라면 재귀함수를 통해 다음 자리를 채워나갑니다.
      4. 그렇지 않다면 다음 반복문으로 넘어가 다른 수로 해당 자리를 채웁니다.