[골드5] 2023번 : 신기한 소수

🛠 문제

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

👩🏻‍💻 해결 방법

우선 시간초과로 인해 맞지 않는 풀이었다...
맨 왼쪽에 올 수 있는 수는 (2, 3, 5, 7) 이므로 하나씩 시작점(?)으로 하여 makePrime함수를 호출해주었다
그리고 하나씩 오른쪽에 올 수 있는 숫자들(홀수)를 붙여주면서 해당 값이 소수이면 makePrime을 재귀적으로 호출해주었다
n자리까지 도달했을 경우(n == 0) 값을 출력해주었다

소스 코드

def isPrime(n):
  if n < 2: return False
  cnt = 0
  for i in range(2, n):
    if n % i == 0:
      cnt += 1
      break
  if cnt == 0:
    return True
  else:
    return False
  
n = int(input())

def makePrime(first, n):
  if n == 0:
    print(first)
  
  for i in [1, 3, 5, 7, 9]:
    tmp = first*10 + i
    if isPrime(tmp):
      makePrime(tmp, n-1)

for i in [2, 3, 5, 7]:
  makePrime(i, n-1)

💡 다른 사람의 풀이

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

    if len(num) == n: 
      print(num) 
      return 
      
    for p in prime: 
      find(num+p) 
      
n = int(input()) 
start = ['2', '3', '5', '7'] 
prime = ['1', '3', '7', '9'] 
for s in start: 
  find(s)