-
2023. [Python] 신기한 소수Python_알고리즘/Gold V 2024. 2. 25. 15:10
1. 문제
https://www.acmicpc.net/problem/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(깊이 우선 탐색)
'Python_알고리즘 > Gold V' 카테고리의 다른 글
1456. [Python]거의 소수 (0) 2024.04.14 1916. [Python]최소비용 구하기 (1) 2024.03.05 9205. [Python] 맥주 마시면서 걸어가기 (0) 2024.02.18 1593. [Python]문자 해독 (1) 2023.12.28 1263. [Python]시간 관리 (1) 2023.12.21