백준 2023번 - 신기한 소수

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

소수를 판별하는 부분을 백트래킹으로 확인하는 문제이다.

 

왼쪽부터 차례로 소수인지를 판별한다는 점에 착안해서 1의 자리에서 부터 차례대로 소수인지를 검사했다.

1의 자리에서 소수가 2,3,5,7이기 때문에 N이 2일때는 4개의 수에 대해서만 자리수를 하나 늘려주고

1의 자리에 1부터 9까지 검사하도록 했다.

 

이를 N만큼 반복해주는 식으로 문제를 풀었다.

오름차순으로 정렬을 해야하기 때문에 큐를 사용해서 먼저 값이 들어간 순서대로 검사를 할 수 있도록 했다.

#include <iostream>
#include <queue>
using namespace std;
 
int N;
queue<int> q;
 
bool prime(int num){
    for(int i=2;i*i<=num;i++){
        if(num%i==0)
            return false;
    }
    return true;
}
int main(){
    
    cin>>N;
    
    q.push(2); q.push(3);
    q.push(5); q.push(7);
    
    bool check=true;
    int num=0;
    int size=q.size();
    
    for(int i=1;i<N;i++){
        for(int j=0;j<size;j++){
            
            check=true;
            num=q.front();
            q.pop();
            
            for(int k=1;k<10;k++){
                if(prime(num*10+k))
                    q.push(num*10+k);
            }
        }
        
        size=q.size();
    }
    
    while(!q.empty()){
        cout<<q.front()<<endl;
        q.pop();
    }
    return 0;
}