[코딩테스트][백준] 🔥 백준 2023번 "신기한 소수" 문제: Python으로 완벽 해결하기! 🔥

문제 링크

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

🕒 Python 풀이시간: 20분

import math

def isPrimeNum(num):
    for i in range(2,int(math.sqrt(num))+1):
        if num%i==0:
            return False
    return True

def dfs(deep,s):
    global answer
    if not isPrimeNum(int(s)):
        return
    if deep==n-1:
        answer.append(s)
    for i in range(1,10):
        dfs(deep+1,s+str(i))

answer=[]
n=int(input())
for i in range(2,10):
    dfs(0,str(i))

for a in answer:
    print(a)

소수로 이루어진 N자리 수 찾기 🔍✨

앞에서부터 한자리씩 끊었을 때 모든 수가 소수가 될 수 있는 수를 구하는 문제이다. N이 주어지면 N자리의 수를 구하며 N은 최대 8까지 가능하다.

간단하게 DFS로 구할 수 있는 문제이다. 백트래킹이라고도 한다. 각 DFS를 자리에 대해 뒤에 한자리씩 붙이며 진행하면서 해당 수가 만들어진 수가 소수가 아니라면 흐름을 끊으며 나아간다. 결과적으로 N까지 완성되고 그 수가 소수가 된다면 그 자리까지 숫자가 이어지는 모든 흐름의 수가 소수가 되는 수이기 때문에 이를 정답에 담아서 출력하면 된다.

이렇게 Python로 백준의 "신기한 소수" 문제를 해결해보았습니다. 코드와 개념 설명을 참고하여 문제를 해결하는 데 도움이 되셨길 바랍니다! 😊