백준 2023 신기한 소수, 파이썬

문제

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

풀이

문제를 처음 읽고는 내가 지금 생각하는 방식으로 문제를 해결한다면 엄청난 시간초과가 발생할거 같다는 생각을 했다.

그러다 결국 구글 검색 찬스를 사용했다....

코드

import sys
input = sys.stdin.readline


n = int(input())

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


def dfs(num):
    # n 자릿수 도달 시 멈춤
    if len(str(num)) == n:
        print(num)
    else:
        for i in range(10):
            temp = num * 10 + i
            # 10 곱하고 i 더해서 자릿수 늘린 수가 소수일때만
            if find(temp):
                dfs(temp)

# 한자리 숫자 중에 소수로 시작
dfs(2)
dfs(3)
dfs(5)
dfs(7)

애초에 첫번째 숫자를 소수로 시작해서 dfs를 돌리는 방법이 있다는 것을 알게 됐다!