[Java] 2023번: 신기한 소수

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

2023번: 신기한 소수

---

💡 접근 방법

1. 문제 이해

7331은 신기한 소수이다. 이유는 7 / 73 / 733 / 7331 이 모두 소수이기 때문이다. 그러면 앞에서부터 뒤에 숫자를 붙여주면서 소수인 경우 백트레킹을 돌려주면 되는 문제다.

 

우선 소수를 구하는 코드는 여러 가지의 방법이 있다. 여기서 나는 제곱근을 이용해서 소수를 구 할 생각이다.

private static boolean isPrime(int number) {
	if (number <= 1) return false;

	int range = (int) Math.sqrt(number);
	for (int i = 2; i <= range; i++) {
		if (number % i == 0) return false;
	}

	return true;
}

 

2. 문제 풀이

우선 탈출조건으로 길이가 N인 경우 소수인지 판별하고 소수가 맞을 경우 정답에 추가를 해준다. 여기서 정답은 많은 경우가 나올 수 있으므로 StringBuilder를 사용해서 출력을 한다.

if (depth == N) {
	if (isPrime(number)) answer.append(number).append("\n");
	return;
}

 

7331을 예로 들면 처음에 7 -> 73 -> 733 -> 7331로 순차적으로 소수인지 판별하면 된다. 처음의 값 0을 시작으로 소수인지 판별하고 7331처럼 7 이 소수이므로 백트레킹 다음 타겟으로 7을 넘겨준다 그런 다음 반복문을 통해서 71, 72, 73, 74, 75, ... 와 같이 소수를 찾는다.

for (int i = 1; i <= 9; i++) {
	int temp = number * 10 + i;
	if (isPrime(temp)) {
        backtracking(temp, depth + 1);
	}
}

 

생각보다 쉽게 풀어서 골드보다는 실버에 가까운 문제가 아닌가 싶었다.

---

 

🗝 풀이 코드

import java.util.Scanner;

public class Main {

    static int N;
    static StringBuilder answer;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        answer = new StringBuilder();

        backtracking(0, 0);

        System.out.println(answer);
    }

    private static void backtracking(int number, int depth) {
        if (depth == N) {
            if (isPrime(number)) answer.append(number).append("\n");
            return;
        }

        for (int i = 1; i <= 9; i++) {
            int temp = number * 10 + i;
            if (isPrime(temp)) {
                backtracking(temp, depth + 1);
            }
        }
    }

    private static boolean isPrime(int number) {
        if (number <= 1) return false;

        int range = (int) Math.sqrt(number);
        for (int i = 2; i <= range; i++) {
            if (number % i == 0) return false;
        }

        return true;
    }
}