(JAVA) 백준 2023번 : 신기한 소수 --- [백트래킹]

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

2023번: 신기한 소수

 

안녕하세요.

 

이 문제는 백트래킹 + 소수 문제입니다.

 

소수를 구하기 위해 에라토스테네스의 체 를 이용했어요.

 

에라토스테네스의 체 가 궁금하면 아래 포스팅을 참고해주세요.

https://maivve.tistory.com/65

(JAVA) 백준 2960번 : 에라토스체네스의 체

 

처음에 어떻게 할 지 고민하다가, 1 ~ N 까지 배열로 잡고 에라토스체네스의 체 로 소수를 만들어놓고 해볼까? 하다가

N <= 8 이기에, 천만자리까지 진행하기에는 비효율적이다 라고 판단했습니다.

 

그럼, 한 자리마다 for문으로 하나씩 탐색해가면서 그 자리 숫자(~~~0 부터 ~~~9까지) 만 놓고 소수를 찾으면 어떨까? 했습니다.

 

이렇게 하면, 굳이 필요없는 숫자들까지 소수 판단을 하지 않아서 경우의수가 줄어들기 때문에 효율적이라고 생각했습니다.

 

 

 

매커니즘

---

  1.  1자리의 소수는 2, 3, 5, 7로 고정이므로, 이를 별도의 String 배열에 넣고 for문을 돌립니다. 또한, 뒷 자리에 올 수 있는 수는 짝수와 5를 제외한 나머지(1, 3, 7, 9) 만 가능하므로, 이 또한 별도의 String 배열에 넣습니다.

 

  2.  그리고 백트래킹 함수를 호출합니다.

   *** 파라미터는 이전까지의 소수 String과 이전까지의 소수 자리수 len 

 

  3.  이전까지의 소수 문자열 끝에 (1, 3, 7, 9) 중 하나를 더해 새로운 숫자(String을 int로 변환) 를 만들어, 이 숫자가 소수인지 체크합니다. 체크를 위해 Math.sqrt()는 필수! 

    *** 여기서 에라토스테네스의 체 를 사용.

 

  4.  1 ~ 3 과정을 통해 N자리 수 까지 구했다면, 이 문자열을 StringBuilder에 저장합니다.

 

  5.  모든 과정이 끝나고, StringBuilder에 저장되어있는 문자열 출력!

 

 

 

이상입니다. 궁금한 사항은 아래 소스코드 및 주석을 참고해주세요!

 

 

감사합니다!

 

 

 

 

소스코드

---