백준2023 - 신기한 소수 Python

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

해당 문제는 각 자리수가 모두 소수이며 길이가 N인 숫자를 모두 출력하는 문제다.

 

문제 풀이 방식

소수를 판정하는 함수를 만들어두고, 다음 만들 수 있는 수가 소수인 경우만 DFS 알고리즘에 인자로 던져주는 방식으로 로직을 완성했다.

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read().splitlines()

def solution (data) :
  K = int(data[0])
  result = []
  
  def isPrime (n) : 
    if n <= 1 : return False
    for i in range(2, int(n ** 0.5) + 1) :
      if n % i == 0 : return False
    return True
    
  def DFS(n) :
    if K == len(str(n)) : 
      result.append(n)
    else :
      for i in range(1, 10) : 
        temp = n * 10 + i
        if isPrime(temp) : DFS(temp)
  
  for i in range(2, 10) :
    if isPrime(i) : DFS(i)
  
  print('\n'.join(map(str, result)))
  
solution(input_data)