문제

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

소스코드 1

if __name__ == "__main__":  
    def check(sosu):
        v = int(sosu)
        for i in range(2,int(v**0.5)+1):
            if v % i == 0:
                return False
        return True
    def dfs(val,cnt):
    	global res
        if cnt == n:
            res.append(int(val))
            return
        for i in range(10):
            tmp = str(val) + str(i)
            if check(tmp): #소수면
                dfs(tmp,cnt+1)
            
    n = int(input())
    res = []
    for i in [2,3,5,7]:
        dfs(i,1)
    for i in res:
    	print(i)

소스코드 2 (개선)

if __name__ == "__main__":  
    def check(sosu):
        for i in range(2,int(sosu**0.5)+1):
            if sosu % i == 0:
                return False
        return True
    def dfs(val,cnt):
        if cnt == n:
            print(val)
            return
        for i in range(10):
            tmp = val*10 + i
            if check(tmp): #소수면
                dfs(tmp,cnt+1)
            
    n = int(input())
    res = []
    for i in [2,3,5,7]:
        dfs(i,1)

설명

DFS 를 이용해서 첫번째 수 부터 소수인지 판별하고 맞으면 그 다음 수를 추가해서 그 수가 소수인지 판별하면 된다.

처음에 시간 초과가 발생해서 대체 왜인지 찾았는데 나는 소수를 판별할 때 2부터 자기자신 직전까지 전부 다 탐색한 셈이다 근데 이렇게 하면 시간초과남 ;; 이럴 때 필요한 개념이 '에라토스테네스의 체' 이다.

에라토스테네스의 체란?

어떤 수의 소수 여부를 확인할 때, 특정한 숫자의 제곱근 까지만 약수 여부를 검증하면 O(N^1/2)의 시간 복잡도로 빠르게 구할 수 있다.
대량의 소수를 한꺼번에 판별하는 경우 이 개념을 사용한다.

int(sosu**0.5)+1
반드시 +1 해줘야지 제곱근이 포함된다!

후기

• 처음에 시간초과가 나서 소수 판별에는 문제가 없다고 생각해서 dfs 내부 for문 탐색 시 1부터 9까지 숫자를 붙여서 탐색하는게 아니고 1,3,5,7,9만 붙여서 탐색했다 -> 오답임

• 에라토스테네스의 체에서 +1 을 안해줘서 제곱근이 포함되지 않게 소수를 체크해줌 -> 오답

• 나는 수를 붙일 때 문자로 변경해서 해당값을 붙이고 또 다시 정수화하여 판별했는데, 수를 붙일 때 기존 숫자에 * 10 을 한 후 다음 숫자를 붙이면 훨씬 간단하게 코드를 작성할 수있다. (소스코드2에 수정한 코드 추가)

• cnt == n이 되면 res 결과값 배열에 값을 넣어서 마지막에 res 를 출력했는데 그냥 바로바로 출력하면 된다. 근데 사용하는 시간이랑 메모리는 동일하다;; 그냥 훨씬 깔끔한 소스가 된다.