백준 2023 (신기한 소수)
백준 백준 2023 (신기한 소수)
문제 링크
문제 링크 : https://www.acmicpc.net/problem/2023
문제 접근
반갑습니다. 오늘도 재밌는 문제를 들고 왔습니다. 문제를 간략하게 설명해보겠습니다.
수빈이는 소수를 좋아한다고 합니다. N자리 자연수 중, 왼쪽에서부터 1,2,3,..N자리 모두 소수인 신비한 소수를 구하는 문제입니다. 일단 1자리 소수는 2,3,5,7이라고 자명하게 알 수 있습니다.
두 번째로, N자리 신비한 소수면, 왼쪽에서부터 N-1자리까지 분리한 수도 신비한 소수여야 합니다. 그렇다면 이를 활용해서, top-down or botton-up 방식으로 해결할 수 있어 보입니다. 하지만 top-down으로는 해결할 수 없습니다. 왜냐하면 결과를 모르기에, 결과를 분리해서 시작으로 도달하는 top-down 방식은 불가능하다는 의미입니다.
bottom-up 방식으로 해결해봅시다. 그에 앞서, 어떤 N-1자리 자연수가 신비한 소수를 알았습니다. N자리 신비한 소수를 만들기 위해, N-1자리 신비한 자연수에서 0~9에 해당하는 자연수를 붙여 보자는 것입니다. 하지만 생각을 조금 더 해봅시다. 뒷자리가 0,2,4,6,8이라면 절대 소수가 아닙니다. 왜냐하면 짝수가 되기 때문입니다. 그러면 1,3,5,7,9의 경우가 남는데, 사실 뒷자리가 5로 끝나면 무조건 5의 배수기에, 1,3,7,9의 숫자만 고려하면 됩니다.
이렇게 시작 전, branch pruning과정을 거쳐 하나의 노드에 10개의 자식 노드를 갖는 state-space-tree를 하나의 노드에 4개의 자식을 갖는 state-space-tree로 바꾸었습니다. 상태 공간이 매우 줄어서 행복합니다.
그렇다면 N자리 신비한 소수를 얻기 위해, N-1번째 소수에서 1,3,7,9를 붙인 수가 소수인지만 판별하면 정답을 해결할 수 있습니다. 이제 소수를 판별해봅시다.
n(n>=3)이 소수인지를 판별할 때, 3~(n-1)에 해당하는 모든 수로 나누면 시간 복잡도는 O(n)이 됩니다. 하지만 이는 비효율적입니다. O(sqrt(n))으로 판별하는 방법이 있습니다.
3~(n-1)을 보는 것이 아닌, 3~(int(sqrt(n))+1)까지 보자는 것입니다. 만약 n이 소수가 아니라면, 즉 어떤 두 수 p,q의 곱으로 표현될 수 있다고 가정해보겠습니다. (n=p*q, (p<=q)) p<=q라고 가정했기에, p의 upper bound(=상한)은 sqrt(n)이하입니다. 예시로 125을 표현하기 위해서 25x(25 이상인 수)로 표현을 못하기에, sqrt(n)까지만 보자는 의미입니다.
1
2
3
4
5
6
7
8
def is_prime(n) :
if n&1==1 : #홀수라면
for i in range(3,int(n**0.5)+1) :
if n%i==0:
return False
return True
else : #짝수라면
return False
비트 연산을 사용해서 조금이나마 효율적으로 홀수를 판별하도록 구현했습니다. 축하합니다! 이제 우린 소수를 O(sqrt(n))으로 판별할 수 있게 되었습니다!
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def is_prime(n) :
if n&1==1 : #홀수라면
for i in range(3,int(n**0.5)+1) :
if n%i==0:
return False
return True
else : #짝수라면
return False
n=int(input())
primes=[2,3,5,7]
ends=[1,3,7,9] # 끝 자리가 1 3 7 9 입니다.
cnt=1
while cnt!=n :
new_primes=[]
for prime in primes :
for end in ends :
if is_prime(prime*10+end) :
new_primes.append(10*prime+end)
primes=new_primes
cnt+=1
for prime in primes :
print(prime)
초기 소수를 2,3,5,7로 초기화했고, ends 변수에 끝 자리에 올 수 있는 숫자를 저장했습니다. n자리 소수를 가지고, n+1자리 수를 만들었습니다. 만약 소수라면 new_primes list에 추가했고, 이를 새롭게 갱신하는 방식으로 구현했습니다. backtracking 문제입니다.
마무리하며
저는 평소에 backtracking이나 탐색 문제를 재귀함수로 많이 풀었습니다. 하지만 메모리를 많이 사용한다는 단점이 있었습니다. 물론 꼬리재귀를 사용하면 된다지만 . . 안 될때가 있기 마련입니다. 실제로 예전에 재귀함수로 PS를 했다가 메모리 초과가 나서 답을 못낸 경험이 있었기에, 이번에는 while문을 사용하여 구현해보았습니다.