[BOJ/백준][Gold5] 2023 : 신기한 소 (C++)

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

2023번: 신기한 소수

 

 

[난이도] Gold5
[유형] 브루트포스

[풀이]
N자리수 수를 모두 검사하면 시간초과가 나므로
필요없는 것을 걸러주면서 모든 가능한 케이스를 찾아야 한다.
1. prev,cur vector를 선언, prev에는 (i-1) 자리수의 소수를 저장하고,
cur에는 prev에 1자리수를 추가해서 새롭게 확인된 i자리수의 소수를 저장한다.

2. prev,cur 초기화는 {2,3,5,7}로 하고, 뒤에 수를 새롭게 더할 때는 홀수만을 더한다. (짝수가 1의 자리에 오면 소수가 될 수 없다.)

3. prev의 수들에 홀수들 더한 수가 소수인지를 체크할때는 sqrt를 이용해서 연산 시간을 줄인다.

 

#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;
int N;
bool prime(int n){
    for(int i=2;i<=sqrt(n);i++)
        if(n%i==0) return 0;
    return 1;
}
int main(){
    scanf("%d",&N);
    vector<int> prev,cur;
    prev = {2,3,5,7};
    cur=prev;
    for(int i=1;i<N;i++){   
        cur.clear();
        for(int v : prev) {
            for(int j=1;j<10;j+=2){
                int a = v*10+j;
                if(prime(a)) cur.push_back(a);
            }
        }
        prev=cur;
    }
    for(auto a : cur) printf("%d\n",a);
}

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/2023.cpp