백준 - 신기한 소수

문제

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

2023번: 신기한 소수

 

---

풀이

import sys
input = sys.stdin.readline

n = int(input())

def isPrime(num):   # 소수 구하기
    for i in range(2, int(num/2+1)):
        if num % i == 0:
            return False
    return True

def dfs(number):
    if len(str(number)) == n:
        print(number)
    else:
        for i in range(1, 10):
            if i % 2 == 0:  # 짝수일 경우 소수 제외
                continue
            if isPrime(number * 10 + i):    # i를 뒤에 붙인 새로운 수가 홀수이면서 소수일때
                dfs(number * 10 + i)

# 일의 자리 소수는 2,3,5,7 이므로 4가지 수 에서만 시작
dfs(2)
dfs(3)
dfs(5)
dfs(7)

 

---

설명

아예 접근 조차 못했던 문제

 

- 어차피 한자리 한자리 숫자가 다 소수여야 하니까 소수에 10을 곱하고 0~9까지 더해서 숫자들을 추려주는 방식 사용 -> 시간초과 발생 X

- 두 자리 이상일 때 맨 앞자리는 소수만 가능(2,3,5,7), 나머지 자리는 홀수만 가능!!

그래서 앞자리 만드는 것부터 시작(2,3,5,7)