(C++) - 백준(BOJ) 2023번 : 신기한 소수 답

www.acmicpc.net/problem/2023

2023번: 신기한 소수

간단한 backtracking문제였습니다.

 

풀이방법

 1. 소수인지 판단 소수라면 다음 단계로 간 후 이전 수 * 10 + 1~9까지 대입해서 소수인지 판단

 2. depth(n-1)까지 도달했다면 답 vector에 push

 

Code

#include <iostream>
#include <vector>
using namespace std;
vector <int> ans;

bool isPrime(int num){
    for(int i = 2; i*i <= num; i++){
        if(num % i == 0) return 0;
    }
    return 1;
}

void backtracking(int now,int depth,int n){
    if(isPrime(now)){
        if(depth == n){
            ans.push_back(now);
            return;
        }
        for(int i = 1; i < 10; i++){
            backtracking(now*10 + i, depth+1, n);
        }
    }
}

int main(){
    int n;
    cin >> n;
    for(int i = 2; i < 10; i++)
        backtracking(i, 1, n);
    for(int i  =0; i < ans.size(); i++){
        cout << ans[i] << '\n';
    }
}