[Algorithm] 백준_2023번: 신기한 소수

오늘의 문제는 🚀 백준 2023 신기한 소수이다.

아찔한 문제.. 실력이 차근차근 쌓여서 뚝딱뚝딱 풀어버렸으면 좋겠다ㅎ

테스트케이스 이해하기

N자리 숫자 중에서 앞에서 부터 하나씩 숫자를 끊어봐도 다 소수인 숫자를 찾는 문제이다!

1차 시도 : 실패

• is_prime만 쓰니깐 ⇒ 시간초과

• 에라토스테네스의 체 ⇒ 메모리 초과

  그 뒤로도 한참을 고민했지만.. 방법을 찾지못해서 SOS를 쳤다.

n=int(input())
start_num=10**(n-1)
end_num= 10**n-1

check = [True]*(end_num+1)
check[0] = check[1] = False

#에라토스테네스의 체
for i in range(2, end_num+1):
    if check[i]:
        j = 2*i
        while j<=end_num:
            check[j] = False
            j +=i

def is_prime(x):
    if x<2:
        return False
    i=2
    while i*i<=x:
       if (x%i==0):
           return False
       i +=1

    return True

result=[]
while start_num <= end_num:
    if check[start_num]:
        inside = start_num//10
        count =0
        for i in range(n):
            if not check[inside]:
                break;
            else:
                count +=1
                inside = inside//10
        if count == n-1:
            result.append(start_num)
    start_num +=1

for i in range(len(result)):
    print(result[i])

2차 시도 : 성공

결국, 검사 범위를 줄여서 시간을 단축하는 방법 밖에는 없었다.

• 일단 한자리 수에서 소수여야 하기 때문에 무조건 2, 3, 5, 7 로 시작해야 한다.
• 마찬가지로 짝수이면 소수일 수가 없기 때문에 무조건 1, 3, 5, 7, 9로 끝나야 한다.

이로써 범위가 굉장히 줄어들었다.

재귀 함수를 만들어서 n의 길이가 될 동안 하나씩 추가해서 그때 마다 소수인지 확인하면서 재귀를 돌린다.

정말 재귀를 돌려서 풀꺼라고는 생각을 못했다.

많이 배웠다. 소수의 조건을 곰곰히 생각하고 범위를 확연히 줄이는 방식!

잘 안풀리면 문제를 열심히 더 쳐다봐야겠다.✨

정답코드

n=int(input())

head = ['2','3','5','7']
tail = ['1','3','5','7','9']

def is_prime(x):
    if x<2:
        return False
    i=2
    while i*i<=x: #x를 루트하는 것보다 i를 제곱해줌
       if (x%i==0):
           return False
       i +=1

    return True

def find_prime(x):
    if len(x) == n:
        print(x)
        return

    for i in range(5):
        if is_prime(int(x+tail[i])):
             find_prime(x+tail[i])

for i in range(4):
    find_prime(head[i])

🚀Reference: 백준 2023 신기한 소수