2023. [Python] 신기한 소수

1. 문제

 

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

2023번: 신기한 소수

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 4MB
• DFS(깊이 우선 탐색)

 

3. 파이썬 코드

 

# 재귀 제한 풀기
import sys
sys.setrecursionlimit(10000)
# DFS 함수
def backtracking(total, cnt):
    # 횟수가 N과 같으면
    if cnt == N:
        # 값 출력 후 리턴
        print(total)
        return
    # 2째 자리부터는 1, 3, 7, 9 홀수만 뒤에 붙을 수 있음
    for num in num_list:
        # 만들어진 값의 절반정도까지 2씩 증가해가며 소수인지 판단
        for i in range(3, int(total + num)//2,2):
            # 소수가 아닌 경우 반복문 탈출
            if int(total+num) % i == 0:
                break
        # 소수인 경우 DFS 실행
        else:
            backtracking(total+num, cnt + 1)

N = int(input())

num_list = ["1","3","7","9"]
ans_list = ["2","3","5","7"]

if N == 1:
    for ans in ans_list:
        print(ans)
else:
    for ans in ans_list:
        answer = ans
        backtracking(answer, 1)

 

4. 문제를 풀고난 후 생각

 

• 처음 생각했던 방식은 에라토스테네스의 체를 생각했지만, 메모리가 4MB이고 N의 범위가 10^8이기 때문에 다른 방식으로 생각을 했다.
• 1의 자리의 소수값들에 이후에 값을 붙여나가며 소수인지 체크하는 방식으로 문제를 풀었다.
• 2자리 이상의 소수들은 1, 3, 7, 9 의 숫자들만 붙을 수 있기 때문에 이를 고려하고 반복문을 진행시켰다.
• 반복문 값을 2씩 증가시키며 소수인지 판단을 진행했고, 소수인 경우 다음 숫자를 더해나가는 방식으로 접근함.
• Python3 로는 시간초과가 나지만 Pypy3 로는 문제가 통과됨. => Python3 로 통과되는 코드 생각해볼 예정

 

5. 문제를 푸는데 도움이 되는 지식

 

• DFS(깊이 우선 탐색)