코리아텍 저지 1010 접두소수

접두소수 문제를 풀었다.

http://judge.koreatech.ac.kr/problem.php?id=1010

에라토스테네스의 채 알고리즘을 공부한 참에 이걸 이용하려다가... 메모리 초과가 났다.

n이 8까지여서 배열을 array[100000000] 9자리 선언했더니 ..... 

128메가 제한인데 800메가정도 잡힌것? 같다.(정확히는 모르겠다.)  

무튼 계속 시도하다 안됨을 깨닫고.. bfs로 풀었다.

bfs구현은 어려움 없이 구현 되었다. 수를 붙일때마다 소수검사를 해준다.

package koreatech1010; import java.util.*; class Pair{ int num; int cnt; public Pair(int num, int cnt){ this.num = num; this.cnt = cnt; } } public class Main { public static boolean[] isNotSoSoo; public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int n = sc.nextInt(); Queue q = new LinkedList(); q.add(new Pair(2, 1)); q.add(new Pair(3, 1)); q.add(new Pair(5, 1)); q.add(new Pair(7, 1)); while(!q.isEmpty()){ Pair pair = (Pair)q.poll(); if(pair.cnt == n){ System.out.println(pair.num); } int[] di = {1, 3, 7, 9}; for(int i = 0; i < 4; i++){ int temp = pair.num * 10 + di[i]; if(isSoSoo(temp)){ q.add(new Pair(temp, pair.cnt + 1)); } } } } public static boolean isSoSoo(int n){ for(int i = 2; i * i < n; i++){ if(n%i == 0){ return false; } } return true; } }