[백준] 2023번 : 신기한 소수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

2023번: 신기한 소수

 

1. 문제 설명

2. 풀이과정

해당 문제는 재귀 함수에 자릿수 개념을 붙여 DFS를 구현하고 문제 조건에 맞도록 가지치기를 하며 문제를 해결한다.

제일 앞자리부터 모든 수가 소수이어야 하므로 우선 자릿수가 한 개인 소수 2, 3, 5, 7로 시작하는 수를 탐색한다.

두 자릿수 이상부터는 해당 수의 마지막 자릿수가 짝수이면 무조건 소수가 아니므로 짝수를 가지치기한다.

현재 수 * 10 + 새로운 자릿수를 계산하여 해당 수가 소수인지 판단하고 소수이면 재귀 함수로 자릿수를 하나 늘린다.

자릿수를 N까지 확장했을 때 그 값이 소수이면 해당 값을 출력한다.

 

슈도코드

1. N(자릿수) 입력받기
2. 소수 판별하는 함수(num):
   1. for i를 2 ~ 현재 수 / 2 + 1까지 반복:
   2. if (현재 수 % i가 0이면): return False (소수가 아님)
   3. return True (소수임)
3. DFS 함수(num):
   1. if (자릿수 == N): 현재 수 출력
   2. else:
   3. for i를 1 ~ 9 반복:
   4. if (i가 짝수이면): continue (소수가 될 수 없음)
   5. if (현재 수 * 10 + i가 소수인지 판별하고 소수이면): DFS(현재 수 * 10 + i) 실행
4. DFS(2), DFS(3), DFS(5), DFS(7) 탐색 시작

반응형

3. 소스코드

import sys

N = int(sys.stdin.readline())

def isPrime(num):
    for i in range(2, int(num / 2 + 1)):
        if (num % 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 (isPrime(num * 10 + i)):
                DFS(num * 10 + i)

DFS(2)
DFS(3)
DFS(5)
DFS(7)