[백준]2023번 신기한 소수(JAVA)

0. 문제 링크

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

2023번: 신기한 소수

 

1. 문제 설명

1) N 자리 수 중에서 왼쪽부터 1자리, 2자리, ... , N자리가 모두 소수인 수 찾기

 

2. 입출력

// input
4

// output
2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393

 

3. 코드

import java.util.Arrays;
import java.util.Scanner;

public class b2023 {
	static int N;
	static int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
	static int[] sel;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt(); // N 자리 수
		sel = new int[N]; // 선택한 숫자
		makeDemical(0);
	}

	// idx : 원본 배열 인덱스, k : 선택 배열 인덱스
	private static void makeDemical(int k) {
		int temp; // 배열을 숫자로 만들 변수
		
		// basis part
		if(k == sel.length) { // 여기까지 선택했을 때 이미 소수이므로 소수 판별할 필요가 없음
			temp = 0;
			for(int j = 0; j < k; j++) { // 현재까지 배열 숫자로 만들기
				temp += sel[j] * Math.pow(10, k-1-j);
			}
			System.out.println(temp);
			return;
		}
		
		// inductive part
		for(int i = 0; i < arr.length; i++) {
			if(k == 0) { // 처음에는 소수로만 시작
				if(isPrime(arr[i]) == 1) { // 소수이면
					sel[k] = arr[i];
					makeDemical(k+1);
				} 
			} else if(k > 0) { // 한번 뽑은 후에는
				temp = 0;
				
				for(int j = 0; j < k; j++) { // 현재까지 배열 숫자로 만들기
					temp += sel[j] * Math.pow(10, k-j);
				}
				temp += arr[i];
				
				if(isPrime(temp) == 1) { // 현재까지의 수가 소수이면
					sel[k] = arr[i];
					makeDemical(k+1);
				}
			}
		}
	}
	
	// 소수인지 확인하는 함수
	private static int isPrime(int n) {
		if(n == 1) {
			return 0;
		}
		for(int i = 2; i <= (int)Math.sqrt(n); i++) {
			if(n % i == 0) { // 소수가 아님
				return 0;
			}
		}
		return 1;
	}
}

 

실행 결과

 

4. 회고

1) 에라토스테네스의 체의 원리를 이용하여 소수를 판별하는 isPrime 함수 정의

- 1은 소수가 아님

- 2부터 소수를 판별하는 수의 제곱근까지 배수인 수를 제거

2) 재귀를 이용하여 1~9까지 수 중에서 한 자리씩 선택하여 소수이면 계속해서 N자리까지 소수인지 판별

3) 반복문에서 초기식, 조건식, 증감식 변수 반드시 확인하기

+) 골드 문제 해결해따...٩( ᐛ )و 

 

 

5. Github

https://github.com/iihye/Algorithm/blob/main/Baekjoon/b2023.java