[백준_2023번] 신기한 소수

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

2023번: 신기한 소수

[문제]

 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.

 수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.

 

[입력 조건]

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

 

[코드]

import java.util.*;

public class BaekJoon_2023 {
	static int n,count=0;
	static StringBuilder sb=new StringBuilder();
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		
		dfs(0,"");
		System.out.println(sb);
	}
	
	static void dfs(int depth, String num) {
		// n의 자리가 만들어졌다면 추가
		if(depth==n) {
			sb.append(num).append('\n');
			return;
		}
		
		// 1~9까지 소수인지 판별하여 소수라면 문자열 뒤에 붙이고 재귀호출
		for(int i=1;i<=9;i++) {
			if(isPrime(Integer.parseInt(num+i)))
				dfs(depth+1,num+i);
		}
	}
	
	/*
	 * <에라토스테네스 알고리즘>
	 * 2부터 루트n 이하까지 반복하여 n과 나누어 떨어지는 숫자가 있다면 소수가 아님
	 */
	public static boolean isPrime(int n) {
        // 1은 소수가 아니기 때문에 바로 false 처리
		if(n==1)
        	return false;
		
		for(int i=2;i<=Math.sqrt(n);i++) {
        	if(n%i==0)
        		return false;
        }
        
        return true;
	}
}

 

[고찰]

 이번 문제는 백트래킹을 사용하여 해결할 수 있는 문제로 만들어진 수가 소수인 경우만 재귀호출을 하는 방식으로 해결할 수 있다. 이때 소수인지 판별하는 방법은 이전 문제를 통해 구현해봤던 에라토스테네스의 채 알고리즘을 사용하였다. 처음에는 만들어질 수 있는 숫자까지 boolean 배열을 사용하여 미리 소수인지 판별해놓으려고 했지만 그러면 많은 메모리와 시간이 낭비될 것 같아 만들어지는 숫자를 소수인지 판단하는 방식으로 바꿔 해결하였고, 시간초과 없이 정답 처리를 받을 수 있었다.