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

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

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

import java.util.Scanner; public class Main { static int[] prime; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int min = (int) Math.pow(10, n-1); int max = (int) Math.pow(10, n); prime = new int[max]; isPrime(max); for (int i = min; i < max; i++) { if(prime[i] == 0) { if (chk(i)) System.out.println(i); } } } public static boolean chk(int num) { sb.setLength(0); sb.append(num); int cnt = sb.toString().length(); if (cnt == 1 && prime[num] == 0) { return true; } else { for (int i = 0; i < cnt; i++) { String word = sb.substring(0, sb.length()-i); int n =Integer.parseInt(word); if(prime[n] == 1) return false; } return true; } } public static void isPrime(int max) { prime[0] = prime[1] = 1; for (int i = 2; i < max; i++) { if (prime[i] == 0) { for (int j = i * 2; j < max; j += i) { prime[j] = 1; } } } } }

n 의 값을 입력받아 최솟값, 최댓값을 구하여 최댓값 만큼 에라토스테네스의 체를 사용한 후 소수일 때 자릿수별 팰린드롬을 구하려고 했지만, 정답은 맞으나 메모리 초과 문제가 발생했다. 아마 8일 때 연산이 많아져 발생하는 것 같다.

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int n; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); n = Integer.parseInt(br.readLine()); dfs("", 0); System.out.println(sb.toString()); } static void dfs(String str, int num) { if (num == n) sb.append(str).append("

"); else{ for (int i = 1; i <= 9; i++) { String word = str + i; if (isPrime(Integer.parseInt(word))) dfs(word, num+1); } } } static boolean isPrime(int k) { if (k == 1) return false; for (int i = 2; i * i <= k; i++) { if (k % i == 0) return false; } return true; } }

에라토스테네스의 체를 사용하지 않고, dfs로 소수일 때만 다음 자릿수를 탐색 하여 가지치기를 하도록 하니 성공.

from http://sasca37.tistory.com/122 by ccl(A) rewrite - 2021-12-18 13:27:55