[백준 파이썬 2023번]신기한 소수★DFS이용한 재귀
2023. 1. 2. 15:01
728x90
반응형
https://www.acmicpc.net/problem/2023
2023번: 신기한 소수
수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수
www.acmicpc.net
import sys
import math
sys.setrecursionlimit(10000)
N = int(sys.stdin.readline())
def is_prime(num):
for i in range(2, int(math.sqrt(num) + 1)):
if num % i == 0:
return False
return True
def DFS(number):
if len(str(number))==N:
print(number)
else:
for i in range(1, 10):
if i % 2 == 0:
continue
if is_prime(number * 10 + i):
DFS(number * 10 + i)
#N = 2
DFS(2)
# DFS(2) ==> number = 2 ==> len(str(number))=1 != N(2)
# is_prime(2 *10 +1) ==> False
# is_prime(2 *10 +3) == True ==> DFS(2*10 + 3) = DFS(23) ==> len(str(23)) =2 == N ==> print(23)
# is_pime(2 * 10 + 5) == False
# is_pime(2 * 10 + 7) == False
# is_pime(2 * 10 + 9) == True ==> DFS(2*10 + 9) = DFS(29) ==> len(str(29)) =2 == N ==> print(29)
DFS(3)
DFS(5)
DFS(7)==> 재귀에 대한 이해
==> DFS(2) , DFS(3) , DFS(5), DFS(7) ==> 소수에 대한 재귀를 시작하면 된다.
728x90
반응형
'Python(백준) > DFS_깊이 우선탐색' 카테고리의 다른 글
| [백준 파이썬 11724번]연결 요소의 개수 구하기★DFS★edge 리스트★VER3.0 (0) | 2023.01.02 |
|---|