신기한 소수

문제

백준 2023번 - 신기한 소수

언어

Java

순서도

재귀 호출을 이용해서 n 자리의 모든 수 만들어보기
한 자리씩 늘려가는 과정 중에 소수가 아닌 경우는 바로 호출 멈추기
신기한 소수에 해당하는 수만 문자열에 덧붙이기
문자열 출력

문제 풀이 step 1

본 문제는 백 트래킹 문제로 조건을 만족하면 반복을 종료함으로써, 반복의 수를 줄여서 시간 복잡도를 낮추는 알고리즘입니다.
문제에 대한 설명은 다음과 같습니다.
- 신기한 소수란 왼쪽부터 1 자리, 2 자리, 3 자리, 4 자리 수 모두 소수인 경우를 의미합니다.
- 예를 들어, 7331 의 경우, 7331 도 소수, 733 도 소수, 73 도 소수, 7 도 소수입니다.
N 이 주어질 때, N 자리의 신기한 소수를 모두 구하는 문제입니다.

문제 풀이 step 2

우선, 재귀 함수를 이용해서 만들 수 있는 모든 N 자리의 숫자를 만듭니다.
- 모두 만들게 될 경우, 숫자가 너무 많기 때문에 시간초과가 발생합니다.
- 따라서, 백트래킹 기법을 이용해서 불필요한 호출을 제거함으로써 시간초과를 방지합니다.
- 예를 들어, 3 => 31 => 315 => 3153 과 같은 방식으로 만든다고 가정하겠습니다.
- 이때, 매번 소수인지 검사를 통해서 신기한 소수의 조건을 만족하지 않는다면 더 이상의 호출은 하지 않습니다.
- 본 예시에서는 3 은 소수, 31 도 소수지만, 315 는 소수가 아니기 때문에 그 이상의 호출은 의미가 없습니다.
- 그리고 매 호출시 다음 자리에 올 수 있는 숫자는 홀수밖에 없습니다. 따라서 짝수가 오는 경우는 아예 호출을 하지 않음으로써 불필요한 호출은 제거 합니다.
- 단, 1 의 자리에 올 수 있는 수는 2, 3, 5, 7 이기 때문에 호출의 시작은 2, 3, 5, 7 로 재귀 호출을 시작합니다.
위 과정속에서 검사를 통과한 신기한 소수만 모아서 출력하면 정답입니다.
추가 설명은 주석으로 작성하겠습니다.

후기

이번에도 JavaScript 로 제출하니 메모리 초과가 발생해서, Java 로 풀게 되었습니다.
소수 관련 문제인지라 바로 에라토스 테네스의 체를 생각했으나, 범위가 너무 커서 에라토스 테네스의 체를 이용할 수 없었습니다.
에라토스 테네스의 체를 이용할 수 없다면, 그냥 매 숫자마다 소수인지 판별하는 방법으로 우회하는 방법이 좋은 것 같습니다.

소스 코드 1

import java.io.*;
import java.util.*;

public class Main {
	static String res = "";

	// 소수인지 검사하는 함수
	public static boolean checkPrime(int num) {
		for(int i = 2; i * i <= num; i++) {
			if(num % i == 0) return false;
		}

		return true;
	}

	// n 자리의 모든 소수를 만들어보는 함수
	public static void rec(int n, int num, int depth) {
		if(depth == n) {
			res += num + "\n";
			return;
		}

		for(int i = 1; i < 10; i+= 2) {
			int nextNum = num * 10 + i;

			// 소수가 아니라면 더이상의 호출은 의미없음
			if(checkPrime(nextNum) == false) continue;

			rec(n, nextNum, depth + 1);
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();

		// 1의 자리에 올 수 있는 수는 2, 3, 5, 7 밖에 없습니다.
		rec(n, 2, 1);
		rec(n, 3, 1);
		rec(n, 5, 1);
		rec(n, 7, 1);

		System.out.println(res);
	}
}