[백준][JAVA] - 신기한 소수(2023)
문제 소개
🥇️ 문제 레벨 : 골드5
🔔 문제 유형 : 백트래킹, 수학
💬 풀이 언어 : JAVA
⏱️ 풀이 시간 : 15분
🖇️ 문제 링크 : 백준 문제 링크
📝 문제
수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다.
7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.
수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.
🤔 문제 분석
문제에서 요구하는 것은, 수의 길이가 N이면서 7331과 같이 7, 73, 733, 7331 모두 소수인 수를 구하는 것이다.
우선 50 이하의 소수들을 살펴보자.
0, 1, 2, 3, 5, 7
11, 13, 17, 19
23, 29
31, 37
41, 43, 47
위 수들을 통해 알 수 있는 사실은 소수에는 1, 2, 3, 5, 7, 9가 들어간다는 것이다. 즉, 해당 숫자들을 가지고 소수의 조합을 만들면 되는 것이다.
수를 하나씩 채워가면서 만들어진 수가 소수인지 판별하면 되기에 백트래킹이 적합한 문제이다.
😎 최종 코드
메모리 : 11476 KB
시간 : 76 ms
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
public class Main {
static int n;
static int[] primes = {1, 2, 3, 5, 7, 9}, numbers;
static StringBuilder sb;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 입력
n = Integer.parseInt(br.readLine());
br.close();
// 각 자릿수에 맞는 값을 저장할 배열
// 예) {7, 3, 3, 1}
numbers = new int[n];
// 답을 저장할 빌더
sb = new StringBuilder();
// 백트래킹 시작
backTracking(0, 0);
System.out.println(sb);
}
private static void backTracking(int depth, int curNum) {
// 만약 깊이가 n과 동일할 경우 현재 값을 빌더에 추가 후 복귀
if (depth == n) {
sb.append(curNum).append("\n");
return;
}
// 깊이가 n이 아닐 경우 배열을 돌면서 소수 탐색
for (int prime : primes) {
// 가장 앞 자리가 1일 경우 건너뛰기
if (depth == 0 && prime == 1) {
continue;
}
// 현재 자리수에 값 저장
numbers[depth] = prime;
// 배열을 수로 반환
int nextNum = curNum(depth);
// 소수일 경우 다음 자리수를 찾기 위해 백트래킹 진행
if(isPrime(nextNum)) {
backTracking(depth + 1, nextNum);
}
}
}
private static int curNum(int depth) {
int num = 0;
// 수가 존재하는 가장 끝 자리부터 값 구하기
// 733일 경우 3 + 30 + 700
for (int i = depth, j = 1; i >= 0; i--, j *= 10) {
num += (numbers[i] * j);
}
return num;
}
private static boolean isPrime(int num) {
// 주어진 수가 소수인지 판별
for (int i = 2; i <= (int) Math.sqrt(num); i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
}
댓글남기기