반응형
2023번 신기한 소수
https://www.acmicpc.net/problem/2023
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 = {2, 3, 5, 7}; 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 |
반응형
'공부 > Algorithm' 카테고리의 다른 글
백준 골드5 달성! (0) | 2023.08.11 |
---|---|
백준 2644번 촌수 계산 자바(BFS,DFS)로 풀어 본 짧은 글 (0) | 2023.08.03 |
백준 2583번 영역 구하기 자바로 풀어 본 짧은 글 (0) | 2023.07.23 |
알고리즘 근황 (0) | 2023.07.23 |
백준 11822번 Document 자바로 풀어 본 짧은 글 (0) | 2023.06.08 |