[BOJ] 2023. 신기한 소수(Python) / DFS

www.acmicpc.net/problem/2023

2023번: 신기한 소수

원래 8자리로 10 ** 8 짜리 리스트로 에라토스테네스의 체를 사용해 미리 소수 0, 1 테이블을 만들어놓으려고 했는데,

메모리를 보니 4mb로 매우 작아서

• 백트래킹(Backtracking)으로 재귀로 들어오는 temp 값의 소수여부를 확인해 가지치기했다.
• 출력되는 소수값을 자세히 보면
  • 맨 앞자리 수는 2, 3, 5, 7만 올 수 있고
  • 2~N자리 수까지는 1, 3, 7, 9만 올 수 있어서 이를 반영했다.

 

파이썬 코드는 다음과 같다.

---

def dfs(depth, temp):
    # 소수 가지치기. 이 때, 제곱근까지의 값만 나누어 나머지의 여부를 보면 된다!
    for p in range(2, int(int(temp)**0.5)+1):
        if not int(temp) % p:
            return


    # 자릿수 끝에 다다랐을 때 출력
    if depth == n:
        print(temp)
        return

    for i in "1379":
        dfs(depth+1, temp+i)

n = int(input())
for s in "2357":
    solve(1, s)

---

• 고찰 : 어렵지 않은 백트래킹 문제였다. Backtracking / DFS 문제 계속 많이 풀자. 화이팅.