알고리즘/알문풀(백준, 프로그래머스, 코드트리)
[알고리즘] BOJ 2023 신기한 소수 (JAVA)
ragabys
2024. 2. 21. 00:46
https://www.acmicpc.net/problem/2023
2023번: 신기한 소수
수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수
www.acmicpc.net
백준 골드5인 백트래킹 유형 중 한 문제였다.
N과M 같은 기본적인 백트래킹 형태의 문제에 소수 판별 로직을 추가하여 구현하는 문제였는데,
기존에 알려진 에라토스테네스의 체 형태를 boolean 배열로 체크하는 방식으로 시도해봤더니 메모리 초과가 발생했다.
N이 8인 경우 10^8 = 100_000_000 이므로 소수인 값들을 미리 저장해두고 찾아서 쓰는 방식 대신,
백트래킹하면서 소수인지를 확인하며 소수인 경우 다음 depth로 진행하는 방식으로 구현했다.
소수를 판별하기 위해 확인해야 할 수 num을 2부터 num의 제곱근까지 나눴을때
나머지가 0인 수가 없다면, 해당 수는 소수임을 판별하는 방식이다.
import java.io.*;
import java.util.*;
public class boj2023 {
static int N, src, dest;
static StringBuilder sb;
public static boolean isPrime(int num) {
if (num < 2) {
return false;
}
for (int i = 2; i <= (int) Math.sqrt(num); i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
public static void backtracking(int depth, int num) {
if (depth == N) {
sb.append(num).append('\n');
return;
}
for (int i = 1; i <= 9; i++) {
int next = num * 10 + i;
if (isPrime(next)) {
backtracking(depth+1, next);
}
}
}
public static void pre() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
sb = new StringBuilder();
}
public static void main(String args[]) throws IOException {
pre();
backtracking(0, 0);
System.out.println(sb);
}
}
해당 코드의 실행 시간은 다음과 같다.
