[Baekjoon] 백준 2023 신기한 소수 (G5^ / DFS, 소수) - Java

링크

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

2023번: 신기한 소수

 

 

 

문제 해석

N자릿수를 가지는 숫자 중 신비한 소수(자릿수가 N, N-1, N-2, N-3... 이 모두 소수가 되는 소수)를 출력하라

 

 

 

코드

package algo.bj.g5_2023;

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

public class Main2 {
	static StringBuilder sb;
	static int N;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		sb = new StringBuilder();
		
		N = Integer.parseInt(st.nextToken());
		
		dfs(2, 1);
		dfs(3, 1);
		dfs(5, 1);
		dfs(7, 1);

		System.out.println(sb);
	}
	
	private static void dfs(int num, int digit) {
		if (digit == N) {
			if (isPrime(num)) {
				sb.append(num + "\n");
				return;				
			}
		}
		
		for (int i = 1; i <= 9; i+=2) {
			int now = num * 10 + i;
			if(isPrime(now)) {
				dfs(now, digit + 1);
			}
		}
	}

	private static boolean isPrime(int num) {
	    if (num < 2) {
	        // 소수가 아님
	        return false;
	    }

	    if (num == 2) {
	        // 소수
	        return true;
	    }
		for (int i = 2; i <= Math.sqrt(num); i++) {
			if (num % i == 0) {
				// 소수가 아님
				return false;
			}
		}
		// 소수
		return true;
	}
}

 

 

 

코드 해석

N자리의 소수 중 N-1에서 N-(N-1) 자릿수까지 모두 소수인 소수를 구하는 문제입니다.

여기서 볼만한 점은 N-(N-1)이 소수인지를 판정해야 한다는 점이 있습니다.

결국 N자리의 소수 중에서 첫 번째 자릿수가 소수( == N-(N-1) 이 소수 )인 숫자들만이 신비한 소수 판정을 받을 수 있습니다.
1의 자릿수가 소수인 수는 2, 3, 5, 7이 있으므로 첫 번째 자리가 2, 3, 5, 7인 숫자들이 후보군에 오를 수 있습니다.
또한 두 번째 자리부터는 짝수를 가지는 경우 2로 나누어 떨어지기 때문에 1, 3, 5, 7, 9를 가지는 숫자에 대하여 소수 판정을 진행하면 됩니다.

 

발생한 문제 & 해결 방안

에라토스테네스의 채로 문제를 풀이하려다 시간초과가 났다.

 

문제에 따라서 효율적인 코드는 서로 다르다!

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

source : https://github.com/ssh5212/conding-test-practice