[백준] 2023번 파이썬 - DFS 풀이

문제요약 (2023. 신기한 소수)

소수 중에서 각 자리수 별로 나눠도 모두 소수라는 성질을 유지하는 소수를 찾아 출력한다.

ex. 7331 -> 7331, 733, 73, 7 모두 소수 -> 우리가 구하고자 하는 수

정수를 입력 받고, 입력받은 정수 값의 자리 수만을 출력한다.

2부터 증가하면서 소수를 찾으면 시간초과에 걸릴 것이다. 다른 방법을 생각해봐야한다.
또한 뒷 자리수부터 숫자가 제거된다는 사실도 문제 해결의 키로 작용할 것이다.

 

2023번: 신기한 소수

 

풀이를 위한 부연 설명

• 뒷자리 수 부터 제거 되므로 str과 int를 써서 문자열 제거 형식으로 진행해도 된다.
• 그러나 해당 방법보다는 처음부터 int 형을 쓰고 * 10으로 자리수를 올리는 방식을 사용해도 된다.
  • ex. 12 를  앞으로 하고 뒤에 숫자 3를 붙이고 싶다면 12 * 10을 하고 3을 더해주면 된다.
  • 앞 숫자 * 10 + 뒷 숫자
• 자리수 단위로 나누었을 때 소수가 되어야하므로 1의 자리수, 2의 자리수, 3의 자리수 소수가 연결되어야한다
  • 그래프 형태로 만들어서 검사할 수 있다.
  • 이때 뒤에 붙는 숫자가 짝수면 안된다. -> 2단위로 늘려가며 뒷자리 늘이기
• 자리수를 늘일 때 앞자리 수 쪽에서 잘랐을 때 소수가 아니라면 뒤에 어떤 숫자를 붙여도 우리가 원하는 "신기한 소수"가 될 수 없다.
  • ex. 21은 소수가 아니다. 여기에 1, 3, 5, 7, 9를 붙여 만든 211, 213, 215, 217, 219 모두 "신기한 소수"가 될 수 없다.
  • ex. 23은 소수이다. 여기에 1, 3, 5, 7, 9를 붙여 만든 231, 233, 235, 237, 239 모두 "신기한 소수"가 될 수 있는 수가 있다.
  • 만약 n-1 자리수에서 "신기한 소수"가 아니라면 n 자리수 "신기한 소수"를 구할 때 앞에 들어갈 수로 생각할 필요가 없다.
  • -> DFS 로 필요한 수만 찾아보자
• 자리수에 해당하는 "신기한 소수"들을 넣어둔다.

• DFS에 대한 개념과 연관 문제는 다음 게시글을 참고하면 된다.

[코테 알고리즘] DFS, BFS / 관련 문제

 

코드

import sys
input = sys.stdin.readline

digit = int(input())
# 신기한 소수들을 넣을 리스트
num = [[], [2, 3, 5, 7]]

def dfs(d):
    num.append([])
    for first in num[d]:
        # 짝수는 뒤의 자리수로 추가할 필요가 없으므로 2씩 건너뛰기
        for plus in range(1, 10, 2):
            new = first * 10 + plus
            # 소수임을 판단해서 "신기한 소수"로 추가할지 판단
            if isPrime(new):
                num[d+1].append(new)

# 시간 복잡도를 계산했을 때 이렇게 소수를 판단해도 됨
def isPrime(n):
    for i in range(2, int(n / 2 + 1)):
        if n % i == 0:
            return False
    return True

# 자리수에 해당하는 값까지 리스트를 만들어서 접근
for d in range(1, digit+1):
    dfs(d)

for i in num[digit]:
    print(i)

 

기억할 점

• DFS 로 풀 생각을 하는 것이 가장 중요한 문제였다. 
• 미리 계산해둔 값을 저장해서 사용한다 -> 그래프로 접근할 생각을 하는 것이 가장 중요할 것 같다.
• 소수인지를 판단할 때 더 좋은 알고리즘을 사용하는 것도 좋은 방식일 수도 있을 것 같다.