반응형

2023번 신기한 소수

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

 

2023번: 신기한 소수

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수

www.acmicpc.net


Comment

 처음에는 소수판별이기 때문에 이전에 배워뒀던 에라토스테네스의 체를 사용하려고 했다. 하지만 이 문제는 메모리제한이 4MB에 N의 범위가 8 즉 최대 10,000,000 천만의 범위이기 때문에 자바의 데이터 최소단위 byte - boolean크기: 1byte로 지정되었을 때 에토체의 boolean배열만 어림잡아 100mb가 넘게된다 때문에 기각.

일반 소수판별 메서드를 생성해서 처리했다.


hint

DFS, 소수판별을 해야한다


Solution

 최종적으로 가지치기 등등 다양하게 하니까 속도가 좀 빨라졌다. 1,3,5,7,9가 아닌 0~10까지 돌렸을 때는 속도가 좀 느렸었다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
import java.io.*;
import java.util.*;
 
 
public class Main {
    static int[] firstPrime = {2357};
    static int n;
    static ArrayList<Integer> magicPrime = new ArrayList<>();//신기한 소수를 담을 리스트
 
//    static int count = 0;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
//        int jari = (int)Math.pow(10, n); // 끝자리까지보기
 
        //4메가면 에토체가 가능한가?
        // 1000000 백만에 1M 4백만이면 끝나는데 안된다.
        //나중에 에토체로 구현되나만 체크해보면 재밌을듯
 
        //한자릿수는 배열을만들자 이걸 가지고 시작
        //이걸로 조합을 다하면 그건 브루트포스아닌가?
        //그래서 DFS느낌으로 가는건가?
 
        //슈도흐름을 생각해보자.
        //1. 한자릿수 prime등록 이후는 전부됨......
        //2. 두번째부터 그 수를 붙여서 prime인지 확인 (n을 입력받은 중단점까지)
        //2_1. DFS를 활용, String에 붙여서 다음 DFS로 이동
        //2_2. 백트래킹도 무조건 넣어야할듯? 한 Depth에서 같은 소수를 여러번 반복해야함
        //3. 중단점을 찾았으면 그 수를 리스트에 추가
        //4. 리스트에 추가된거 출력!
 
        for (int i = 0; i < firstPrime.length; i++) {
            dfs(String.valueOf(firstPrime[i]), 1);
        }
 
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < magicPrime.size(); i++) {
            if(i == magicPrime.size()-1){
                sb.append(magicPrime.get(i));
            }else {
                sb.append(magicPrime.get(i) + "\n");
            }
        }
        System.out.print(sb);
 
    }
 
    static void dfs(String s, int count) {
        if (count == n && isPrime(Integer.valueOf(s))) {//중단점
            magicPrime.add(Integer.valueOf(s));
        }
        if (isPrime(Integer.valueOf(s))) {
            for (int i = 1; i < 10; i += 2) {
                    dfs(s.concat(String.valueOf(i)), count + 1);
            }
        }
    }
 
    static boolean isPrime(int isPrimeNum) {
        for (int i = 2; i <= (int) Math.sqrt(isPrimeNum); i++) {
            if (isPrimeNum % i == 0) {
                return false;
            }
        }
        return true;
    }
}
cs
반응형

+ Recent posts