boj2023 신기한 소수

링크

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

문제

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

7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.

수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

출력

N자리 수 중에서 신기한 소수를 오름차순으로 정렬해서 한 줄에 하나씩 출력한다.

나의 풀이

• dfs 로 1부터 9까지 숫자를 하나씩 붙여가면서 판별한다. 이때, 숫자를 붙이기전에, prime(소수) 인 경우만 재귀하고, 그렇지 않으면 다른 숫자를 붙인다. 이 과정으로 신기한 소수 를 구할 수 있다.
• cnt 가 N 일때, StringBuilder 에 이 숫자를 추가하고 리턴한다.
• 이렇게 풀이하면 어짜피 1부터 9까지 순서대로 숫자를 집어넣으면서 탐색하기때문에, 정렬을 따로 할 필요가 없어서 속도 개선이 가능하다.
• 핵심 코드

• 전체 코드

  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  
  public class boj2023 {
      static int N;
      static StringBuilder sb;
      public static void main(String[] args) throws Exception{
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          sb = new StringBuilder();
          N = Integer.parseInt(br.readLine());
          dfs(0,"");
          System.out.println(sb.toString());
      }
  
      private static void dfs(int cnt,String num){
          if(cnt==N){
              sb.append(num).append("\n");
              return;
          }
  
          for (int i = 1; i <= 9; i++) {
              String temp = num+Integer.toString(i);
              int tempNum = Integer.parseInt(temp);
              if(isPrime(tempNum)){
                  dfs(cnt+1,temp);
              }
          }
      }
  
      private static boolean isPrime(int num) {
          if(num==1)return false;
          for (int i = 2; i*i <= num; i++) {
              if(num%i==0) return false;
          }
          return true;
      }
  }

결과