[백준] 2023번 신기한 소수

💡문제접근

• 백트래킹을 좀 더 공부해보고자 선택해서 풀어본 문제였다.
• 에라토스테네스의 체를 이용하려했는데 N의 값이 점점 커질수록 차지하는 메모리는 점점 커지게 되어 메모리 초과가 발생할 수 있을 것 같아서 일반적으로 사용하는 소수 판별 함수를 작성하여 사용했다.

💡코드(메모리 : 31256KB, 시간 : 48ms)

import sys
input = sys.stdin.readline

N = int(input().strip())

# 소수 판별 함수
def prime_number(x):
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            return False
    return True

# 백트래킹
def recursive(x):
    if len(str(x)) == N:
        print(x)
    for i in range(10):
    	# N자릿수의 숫자를 만들기 위한 식
        val = 10 * x + i
        if prime_number(val):
            recursive(val)

recursive(2)
recursive(3)
recursive(5)
recursive(7)

💡소요시간 : 8m