백준 2023 <신기한 소수> Python

https://www.acmicpc.net/problem/2023

---

소수판정 + 백트래킹 / DP 문제입니다.

우리는 한 자리 소수가 2, 3, 5, 7 이라는 것을 알고있습니다.

그렇다면 두 자리 신기한 소수는 2, 3, 5, 7 로 시작할 것을 알고 있고 그 수들만 소수인지 판정하면 됩니다.

그런 식으로 N 자리 신기한 소수는 N-1 자리 신기한 소수로 시작하므로 점차적으로 자릿수를 늘려가며 탐색하면 됩니다.

 

소수를 판정할 때 모든 수로 나누어가며 판정하는 것은 비효율적이고 에라토스테네스의 체 알고리즘을 통해 최적화를 할 수 있습니다.

 

N 자리 신기한 소수를 찾을 때 N-1 자리 소수를 보고 탐색할 필요가 없는 수를 가지치기할 수 있으므로 백트래킹 알고리즘이라고 할 수 있고, N 자리 소수를 N-1, ... , 1 자리의 소수를 찾는 문제로 나누어 해결할 수 있으므로 DP 문제라고 할 수 있겠습니다.

---

import sys

input = sys.stdin.readline


# 소수 판별
def is_prime(num):
    # 0, 1 이면 False
    if num in [0, 1]:
        return False
    
    # 소수 판별 리스트
    is_primes = [False, False] + [True for _ in range(int(pow(num, 1/2))-1)]
    # 순회
    for i in range(2, len(is_primes)):
        # 현재 수가 소수가 아니면 패스
        if not is_primes[i]:
            continue

        # 현재 수로 수가 나누어 떨어지면 소수가 아님
        if not num % i:
            return False
    
        # 아니면 소수 판별 리스트 업데이트
        for j in range(2*i, len(is_primes), i):
            is_primes[j] = False
    
    # 모두 통과하면 소수
    return True


def solution(N):
    # 신기한 소수 / amazing_primes[i] = [i 자릿수의 신기한 소수들]
    amazing_primes = [['']] + [[] for _ in range(N)]
    ## i-1 자리의 신기한 소수에 수를 붙여 소수면 추가
    # 순회
    for i in range(1, len(amazing_primes)):
        # i-1 자리의 신기한 소수
        for before_num in amazing_primes[i-1]:
            # 수 붙이기
            for num in range(10):
                # 소수 판정을 할 수
                now_num = int(before_num + str(num))
                # 소수 판정
                if is_prime(now_num):
                    # 신기한 소수 추가
                    amazing_primes[i].append(str(now_num))
    
    for amazing_prime in amazing_primes[N]:
        print(amazing_prime)


# 입력
N = int(input().strip())

solution(N)