challenge no.2
[문제]
수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다.
7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.
수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.
[입력]
첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.
1
4
[출력]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393
[풀이]
문제를 보고 가장 먼저 떠오른 풀이 방식
- 소수 구하기
- 그 다음에 n의 자릿수 만큼 조합하기
이 문제의 핵심은 소수를 어떻게 구할 것인지 !
1
2
3
4
5
6
7
8
num_lst = []
def prime_num(num):
for i in range(2, num):
if num % i == 0: #자기 자신까지 숫자로 나누었을때 나눠떨어진다면 -> 소수아님
continue
else:
num_lst.append(i) #나머지는 소수임(2포함)
return num_lst
이 방식으로 풀면 시간복잡도가 크기 때문에 백준을 돌려도 통하지 않는다 !
그래서 보통 소수를 구할때 사용하는 방법 !
바로 “””에라토스테네스의 체””””
→ 입력받은 숫자까지 2이상으로 차례로 나열한 뒤
제곱해서 자신이 되는 수까지 차례대로 나누어서 나머지가 0이 되는 수들을 차례대로 삭제
→ 혼자서 코드로 구현하려고 시도했지만 … 장렬히 실패 …
1
2
3
4
5
6
7
8
dp = [False, False] + [True] * (n-1)
primes = []
def toss(num):
if dp[i]:
primes.append(i)
for j in range(2*i, n+1, i);
dp[j] = False
return primes
이를 통해 소수를 찾는 문제는 해결이 되었고,
이를 이용하여 n의 자리 수까지 소수인지를 탐색하는 함수를 만들면 문제 해결 !
→ 문제 유형 : DFS(재귀함수 or Stack)
1
2
3
4
5
6
7
8
9
10
nums = [1,2,3,5,7,9]
def dfs(strnum):
if len(strnum) ==N:
print(strnum)
return
for n in nums:
newnum =strnum + str(n)
if toss(int(newnums)):
dfs(newnum)