024 신기한 소수

첫번째 코드

 

사실 DFS...아직 어렵다... 책은 정말 똑똑한 친구구나...

023번 문제는 그래도 해당하는 곳에 가서 F를 T로 바꾸고 모두 T가 되면 그만 하는 그런 시스템이라면

024번 문제는 앞의 개념으로 이해하면 소수인 경우에 진행하고 아니면 버리는 식의 재귀 시스템을 돌아가는 코드이다.

DFS는 한번 방문하면 다시 방문하지 않는 시스템인데...그러면 여기서는....

한 자리 수 일때 소수이면 자리수를 추가해서 소수이면 자리수를 추가하고...이런 식으로 다시 한자리 수 일때로 돌아가지 않아서 DFS의 "한번  방문하면 다시 방문하지 않는 시스템"에 포함되는 것인가?

 

import sys
input = sys.stdin.readline

n = int(input())

def prime(x):
    for i in range(2, int((x/2)+1)):
        if x % i == 0:
            return False
    return True

def DFS(num):
    if len(str(num)) == n:
        print(num)
    else:
        for i in range(1, 10):
            if i % 2 == 0:
                continue
            if prime(num * 10 + i):
                DFS(num * 10 + i)
DFS(2)
DFS(3)
DFS(5)
DFS(7) 

 

마음이 매우 굉장히 찝찝한 어려운 통과!

DFS 관련된 문제가 모여있는 곳이 있다면 풀어봐야 할 듯 하다!

그래도 이런 식의 방법도 있다는 것 확인!!!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Gold/2023.%E2%80%85%EC%8B%A0%EA%B8%B0%ED%95%9C%E2%80%85%EC%86%8C%EC%88%98

programmers/백준/Gold/2023. 신기한 소수 at main · ornni/programmers