백준 G4 2023 신기한 소수

문제링크

2023번: 신기한 소수

 

한 줄 아이디어 :

살아남는 수들이 소수이다

 

이 문제는 모든 소수를 찾는 문제가 아니다.

왼쪽에서 1자리 2자리 3자리.. 수가 소수인 아름다운 소수를 찾는 문제다.

 

이를 위해서 DFS를 사용해 1자리 수부터 N자리 수까지 소수가 되는 수만 소수로 출력해보자.

 

예를 들면 1자리 수에서 소수는 2 3 7 이다.

2자리 수에서 소수는 2x , 3x, 7x일 것이다. 3자리 수에서 아름다운 소수는 앞에서 만든 2자리 수에다가 1~9를 붙여보면서 소수가 되는 수 일 것이다.

// 2자리 수에서 아름다운 소수
23
29
31
37
53
59
71
73
79

 

// 2자리 소수에다가 1~9를 붙여서 만든 아름다운 3자리 소수 
233
239
293
311
313
317
373
379
593
599
719
733
739
797

 

정답코드

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

public class Solution {

	static int n;
	static StringBuilder sb;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// n자리
		n = Integer.parseInt(br.readLine());
		sb = new StringBuilder();
		// 재귀
		dfs(0, 0);
		System.out.println(sb.toString());
	}
	
	/**
	 * 
	 * @param depth 자릿수 n자릿수까지 진행한다.
	 * @param num   소수인지 판단할 숫자
	 */
	public static void dfs(int depth, int num) {
		// 주어진 자릿수에 도달하면 출력
		if(depth == n) {
			sb.append(num/10 + "\n");
		}
		
		// 1~9까지의 수를 더해서 소수인지 판단한다.
		for(int i = 1; i <= 9; i++) {
			if(isPrime(num+i)) {
				// 10을 곱해서 넘긴다. ex) 11 => 110 으로 만들어 준다.
				dfs(depth+1, (num+i)*10);
			}
		}
		
		
	}
	
	public static boolean isPrime(int n) {
		// 2보다 작은 수라면 false
		if(n < 2) {
			return false;
		}
		
		// 주어진 수의 제곱근까지 나눠서 소수인지 확인
		for(int i = 2; i*i <= n; i++) {
			if(n % i == 0) {
				return false;
			}
		}
		return true;
	}
}

 

추가적으로 소수 판단 방법은

시간 복잡도가 log N인 주어진 수의 제곱근까지 나눠보면서 이게 나눠지면 소수이고 아니면 소수가 아닌 방법이 있다.