백준 문제풀이 : (2023) 신기한 소수 - C/C++

문제 : https://www.acmicpc.net/problem/2023

2023번: 신기한 소수

 

시간 제한	메모리 제한	난이도	알고리즘 분류
2초	4 MB	Gold 5	수학, 정수론, 백트래킹

 

 

문제

 

 

풀이

소수 구하는 문제를 마주쳤을 때 가장 먼저 떠오르는 풀이법은 에라토스테네스의 체이다. 하지만 소수인지 판별해야하는 수의 최대값은 99,999,999 이므로, 에라토스테네스의 체로 1부터 99,999,999 까지의 판별 정보를 저장하기 위해서는 4MB가 넘는 크기의 배열이 필요하다.

 

따라서 이번 문제에서는 에라토스테네스의 체가 아닌 for 문을 통해 소수인지 판별하는 함수를 사용하기로 한다.

 

문제에서는 왼쪽에서부터 수를 하나씩 붙여, 마지막 자리까지 수를 붙이기까지의 모든 조합이 소수라면 해당 수를 출력하고 있다. TC로 주어지는 숫자가 4일 경우, 답을 구해가는 과정은 아래와 같다.

 

1. 첫번째 수는 2, 3, 5, 7 중 하나이므로(소수여야하므로), 2로 시작하는 숫자 조합부터 맞춰본다. 

2. 숫자 2는 소수이다. 따라서 뒤에 숫자를 추가한다. 뒤에 추가되는 숫자는 무조건 홀수 수여야 한다. (짝수 수일 경우 무조건 소수가 아니게 된다.) 따라서 숫자 1을 추가한다.

        - 숫자 21을 검사한다. 숫자 21은 소수가 아니므로, 해당 경로(21로 시작하는 숫자) 검사는 종료한다. 

        - 만약 검사한 숫자가 소수일 경우에는 2번 과정을 반복한다.

3. 위 2번 항목의 검사 과정을 반복하다가 숫자 자릿수가 N개이고, 소수인 경우 출력하고 해당 루트 검사 종료한다.

 

위 2번을 dfs로 만들기만 하면 문제를 전부 푼 것이나 다름 없다.

 

 

코드 작성

#include <iostream>
#include <cmath>
#define SIZE 100000000

using namespace std;

bool isSosu(int num) { //소수 판별 함수
    for (int i=2 ; i<num/2 ; i+=1) {
        if (num%i==0) return false;
    }
    return true;
}

void dfs(int start, int size, int N) { 
    if (!isSosu(start)) return; //소수가 아니면 해당 경로의 탐색은 중단한다.
    if (size==N) { //소수이면서, N개의 자리가 완성된 경로는 프린트하고 재귀 종료한다.
        printf("%d\n", start);
        return ;
    }
    
    for (int i=1 ; i<=9 ; i+=2) { //홀수 숫자를 붙여나간다. 맨 뒤가 짝수인 수는 무조건 소수가 아니다.
        dfs(start*10+i, size+1, N);
    }
}

int main() {
    int N;
    scanf("%d", &N);
    
    int startNum[] = {2, 3, 5, 7};
    for (int i=0 ; i<4 ; i++) { //첫 숫자는 한자리수 소수에서 시작할 수 밖에 없다.
        dfs(startNum[i], 1, N);
    }
}

 

 

END.