[백준] #2023 신기한 소수(python)

📌문제

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다.

7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.

수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

출력

N자리 수 중에서 신기한 소수를 오름차순으로 정렬해서 한 줄에 하나씩 출력한다.

예제 입력

4

예제 출력

2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393

백준 2023번 문제

💡Idea

계묘년🐰 2023맞이 백준 2023번 문제!

처음에는 아래👇와 같은 로직으로 문제를 해결하려고 했습니다.

1. N자리 수의 왼쪽부터 1자리, 2자리, 3자리...N자리 수까지 차례대로 소수인지를 확인한다.
2. 만약 소수가 아닌 수가 발견되면, 해당 자릿수를 1 증가시킨 뒤 다시 차례대로 소수인지를 확인한다.
3. N자리 수까지 모두 소수이면 정답에 추가한 뒤 해당 수보다 1 증가한 수가 소수인지 확인한다.

하지만 위와 같이 문제를 풀면, 다음과 같은 문제가 발생합니다.

예를 들어 799라는 수에서 1 증가하면 800이 되는데 이 경우 다시 1자리부터 N자리까지 소수인지를 확인해야하는데 이렇게 올림이 되는 경우를 예외처리하기가 복잡해집니다.

따라서 DFS(재귀)를 사용하여 아래👇와 같은 풀이로 문제를 해결하였습니다.

1. 기본적으로 소수임을 알고 있는 2, 3, 5, 7로 시작한다(가장 왼쪽 1자리에 올 수 있는 숫자들은 2, 3, 5, 7만이 가능)
2. 각각 네 개의 숫자 뒤에 0 ~ 9 까지의 숫자를 붙여 두 자리 수를 만든 뒤, 왼쪽에서 2자리까지의 숫자들이 소수인지를 확인한다.
   2-1. 소수라면 만들어진 숫자들 뒤에 다시 0 ~ 9 까지의 숫자를 붙여 세 자리 수를 만들 수 있도록 재귀 함수를 실행한다.
   EX) 2 뒤에 0을 붙인 20은 소수가 아니므로 패스 / 2 뒤에 3을 붙인 23은 소수이므로 다시 230 ~ 239 까지의 숫자들을 만들 수 있도록 함수 실행
3. 2번을 반복하며 원하는 N자리 수까지 확인하며 신기한 소수인 수들을 출력한다.

💻코드

• ⏰ 시간 : 48 ms / 메모리 : 30616 KB

import sys
N = int(sys.stdin.readline())
ans_set = []

def is_prime(x): # 소수 판별 함수
    for i in range(2, int(x ** 0.5) + 1):
        if int(x) % i == 0:
            return False
    return True

def is_surprise(num): # 숫자를 늘려가며 소수인지를 확인하는 함수
    if 10 ** (N - 1) <= num < 10 ** N: # N자리수이면 출력
        print(num)
    else:
        for i in range(10): # 0부터 9까지 숫자 늘리기
            if is_prime(num * 10 + i):
                is_surprise(num * 10 + i)


for i in [2, 3, 5, 7]: # 2, 3, 5, 7로 시작
    is_surprise(i)