[백준 / Java] 2023번: 신기한 소수 (골드5)

문제 풀이 날짜: 2023.08.03
포스트 작성일: 2023.08.03

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 2023번: 신기한 소수 (골드5)

 

키워드

백트랙킹, 소수 판별

 

풀이 접근법

• 1 ≤ N ≤ 8 이므로 백트랙킹을 쓸 수 있다.
• 입력의 크기가 최대 10^8 이기 때문에, 안타깝게도 에라토스테네스의 체를 이용하면 메모리 초과가 나는 문제이다. (메모리 제한 4MB < 4Byte × 10^8)
• 따라서 N자리 수는 그저 중복순열로 생성해주고, 원하는 길이만큼 뽑았다면 자릿수별로 소수가 맞는지 판별한다.
• isPrime() 함수에서는 2부터 number의 제곱근까지 순회하며 나누어 떨어지는지를 검사한다. 나누어 떨어진다면 다른 약수가 있는 것이고, 나누어 떨어지지 않으면 소수이다. O(√N) 시간을 소모한다.
• 도합 O(N! * √N)이 걸리지만 N이 매우 작으므로 시간 초과를 피할 수 있다.

 

코드

import java.io.*;

public class Main {

	private static int N;
	private static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		int[] result = new int[N];
		
		DFS(0, result);
		
		System.out.println(sb);
	}
	
	private static void DFS(int depth, int[] result) {
		if(depth == N) {
			int rslt = 0;
			for(int i = 0; i < result.length; i++) {
				rslt *= 10;
				rslt += result[i];
				
				if(!isPrime(rslt)) {
					return;
				}
			}
			
			sb.append(rslt).append("\n");
			return;
		}
		
		for(int i = 1; i < 10; i++) {
			result[depth] = i;
			DFS(depth + 1, result);
			result[depth] = 0;
		}
		
		return;
	}

	private static boolean isPrime(int rslt) {
		if(rslt == 1) {
			return false;
		}
		
		for(int i = 2; i <= Math.sqrt(rslt); i++) {
			if(rslt % i == 0) {
				return false;
			}
		}
		
		return true;
	}

}

---

메모리 제한을 신경써야 하는 문제이다. 보통은 메모리 초과가 잘 나지 않지만, 이 문제는 입력의 크기와 메모리 제한을 연결지어 생각하는 것이 중요했었다.

 

git 링크

(git 링크 첨부)