[백준] 2023(파이썬) - 신기한 소수

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

2023번: 신기한 소수

• 이 문제는 먼저 소수를 판별해야 하기 때문에 에라토스테네스의 체로 소수인지 아닌지 확인하는 함수를 하나 만들었다.
• 그다음에 계속 삽질을 했던 부분인데, 나는 숫자를 하나씩 소수 판별을 해주기 위해 10으로 나눠 주고, 그 숫자들이 소수인지 아닌지를 확인했는데 이렇게 되면, 어떤 숫자들을 판별해줄 것인가?라는 생각을 하게 된다. 
  예시를 보면 4일 때 4자리 수 들 중 다음 조건과 같은 수들을 뽑아줘야 하는데 내가 처음 생각했던 방법을 생각하면 1000부터 9999까지 이게 조건에 맞는 수인지? 를 판별해주면 시간이 너무 오래 걸리기 때문이다.
• 그래서 생각한 방법은 어차피 한자리 한자리 숫자가 다 소수여야하니까 소수에 10을 곱하고 0부터 9까지 더해서 숫자들을 추려 주는 방식을 사용했다. 그러면 시간 초과가 나지 않는다.
• 한 자리 숫자들 중 소수인건 2,3,5,7 밖에 없으니까 각각의 경우에서 10을 곱하고 0부터 9까지 더해준 뒤, 이 숫자가 소수인지 아닌지를 확인하고 소수일 때만 다시 10을 곱하고 0부터 9까지 더해주고... 이런 방식을 사용했다.
• 그럼 언제 return 값을 받냐? 숫자를 str로 문자열 처리를 해주면 몇 자리 수인지 확인할 수 있고 이 숫자가 입력값과 같을 때 return을 해주면 된다.

import sys
input = sys.stdin.readline
 

n = int(input())

def checkPrimeNum(check_number):
    #에라토스테네스의 체로 소수인지 확인
    for i in range(2, int(check_number**0.5)+1): 
        if int(check_number) % i == 0: 
            return False
    return True

def dfs(num):
	# 목표 길이 도달 시 멈춤
    if len(str(num))==n:
        print(num)
    else:
        for i in range(10):
            temp = num * 10 + i
            # 10곱하고 i 더해서 자릿수 늘린 수가 소수일때만 
            # dfs로 다음 자릿수 확인 넘김
            if checkPrimeNum(temp) == True:
                dfs(temp)
# 맨마지막으로 맨 앞자리를 봤을 떄 소수여야하므로 
# 일의자리숫자중에 소수로 시작을 한다.
dfs(2)
dfs(3)
dfs(5)
dfs(7)