백준 - 2023. 신기한 소수

[백준] 2023. 신기한 소수

Link 골드 5티어 문제

문제

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다.

7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.

수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

출력

N자리 수 중에서 신기한 소수를 오름차순으로 정렬해서 한 줄에 하나씩 출력한다.

예제 입력 1

2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393

풀이

목표는 “신기한 소수”들을 출력하는 것.

입력은 자리수 N이 주어지고, 출력으로 “신기한 소수”를 출력해야한다.

여기서 신기한 소수란 문제에 나와있듯이 왼쪽부터 1,2,…,n 자리 수 모두 소수인 수를 “신기한 소수”라고 한다.

직감적으로 단순히 Brute force를 사용하여 모든 n 자리의 수가 소수인지 아닌지 판별하여 출력한다면 될 거라는걸 알지만, 이 방법으로 할 경우 너무나도 많은 반복이 필요하다.

다행이도 소수에는 간단한 규칙들이 숨겨져있어 이를 이용하여 모든 수에서 소수인 것만 “추출”하는 것이 아니라 “생산”해낸다면 더 적은 반복으로도 문제가 풀릴 것 이다.

어느 방법으로 하든 “소수인지 아닌지”를 판단하는 함수는 필요하기 때문에 미리 만들어 놓고자 한다.

소수의 정의는 “1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수”이다. 이를 참고하여 코드로 옮기면 아래와 같다.

def is_prime(num):
    if num == 1:
        return False
    
    for i in range(2, num):
        if num % i == 0:
            return False
    return True

근데 이 방식으로 소수 판별을 할 경우, 수가 커질수록 상당히 많은 반복이 필요한다.

이를 줄이기 위한 방법은 여러가지가 있지만 내가 선택한 것은 어떤 자연수 K의 제곱근까지만 나누어 떨어지는지 확인하면 소수인지 아닌지 알 수 있다는 점을 이용한 알고리즘이다.

예를들어 25의 약수는 [1, 5, 25]로 \(1\times25\), \(5\times5\), \(25\times1\)로 짝지어진다.

또 16의 약수는 [1, 2, 4, 8, 16]인데 \(1\times16\), \(2\times8\), \(4\times4\), \(8\times2\), \(16\times1\) 으로 짝지어지는데, 16의 제곱근인 4라는 약수를 기준으로 약수끼리 대칭으로 곱하면 해당 수를 만들어낸다.

이처럼 어떤 수의 제곱근을 기준으로 약수가 대칭인 성질을 가지기 때문에 결국 어떤 수의 제곱근까지만 나누어 떨어지는지 확인한다면 소수 판별이 가능하다.

def is_prime(num):
    if num == 1:
        return False
    
    for i in range(2, int(num**0.5)+1):
        if num % i == 0:
            return False
    return True

이제 메인 코드로 넘어가서..

소수에 숨어있는 간단한 규칙은 예를들어 모든 짝수는 2로 나누어떨어지기 때문에 뒷자리가 짝수로 끝난다면 “신기한 소수”는 될 수 없다는 것 이다.

따라서 1번째 자리를 제외한 2,..,n 자리의 수는 홀수여야 한다 -> [1, 3, 5, 7, 9]

1번째 자리에는 특별히 [1, 3, 5, 7, 9]와 2가 자리할 수 있다. (2도 소수니까)

위 규칙을 이용하여 n자리의 소수를 “생산”하는 흐름은 아래와 같다.

1. [1, 2, 3, 5, 7, 9]를 중 하나를 1번째 자리에 넣는다.
2. 그 뒷 자리에 [1, 3, 5, 7, 9]를 하나씩 붙이면서 그 수가 소수인지 아닌지를 판단한다.
   • 소수일 경우 2번을 다시 반복한다.
3. n자리가 수가 되었으면 이를 Print한다.

이를 코드로 옮기면 아래와 같다.

def is_prime(num):
    if num == 1:
        return False
    
    for i in range(2, int(num**0.5)+1):
        if num % i == 0:
            return False
    return True

start = [1, 2, 3, 5, 7, 9]
n = int(input())
def dfs(strnum):
    if len(strnum) == n:
        print(strnum)
        return
    
    for new_num in start:
        temp = strnum + str(new_num)
        if is_prime(int(temp)):
            dfs(temp)
dfs("")