[백준/C++] 1747번: 소수&팰린드롬(S1)

문제

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

1747번: 소수&팰린드롬

 

사용한 알고리즘

2022.01.29 - [PS/Algorithm] - [알고리즘 개념정리] 6. 완전탐색/백트래킹

-> 완전 탐색
각각의 경우들을 좀 더 복잡하게 따져주는 문제이다.
보통 각 경우를 나타내는 무언가를 인수로 받아서 그 경우에 대한 테스트를 진행하는 함수를 따로 작성한다.

 

 

시간 복잡도

문제를 풀기에 앞서, 이 문제를 완전탐색 알고리즘으로 풀어도 되는지 확인해보자.
1 ≤ N ≤ 1,000,000 인데 대충 2백만까지 돌려보면
1,000,000 보다 큰 소수&팰린드롬 중 가장 작은 숫자는 1003001 이라는 것을 알 수 있다.
즉, N으로 어떤 입력이 들어오더라도 1003001 범위 내에서 탐색이 이루어진다.

어떤 수가 팰린드롬인지 판정하는 것은 그 자릿수 만큼의 시간복잡도가 걸리는데
자릿수는 최대 7자리이므로 O(1)이라고 할 수 있다.

어떤 수가 소수인지 판정하는 것은 O(sqrt(N))의 시간복잡도가 걸리며
전처리를 하거나 에라토스테네스의 체를 이용하면 더 빠르게 할 수 있다.

따라서 주어진 숫자부터 1씩 증가시켜 나가면서 소수&팰린드롬인지 체크하는 방식으로도
충분히 통과할 수 있다. 

 

 

풀이

빠른 소수판정을 위해 에라토스테네스의 체를 이용한 전처리를 해주는 함수를 만들자.
참고자료: https://marobiana.tistory.com/91

int not_prime[2000001]; // 소수이면 0, 소수가 아니면 1
void sieve(){
    for(int i=2; i<2000001; i++){
        if(not_prime[i]==0){
            for(int j=2*i; j<2000001; j+=i){
                not_prime[j]=1;
            }
        }
    }
}

 

주어진 수가 팰린드롬인지 확인하는 함수도 만들자.

int palindrome(int n){ //주어진 수가 팰린드롬인지 확인하는 함수
    string s=to_string(n);
    for(int i=0; i<s.length()/2; i++){
        if(s[i]!=s[s.length()-i-1]) return 0;
    }
    return 1;
}

 

이제 n을 1씩 증가시키며 소수&팰린드롬에 해당하는 수를 출력해주면 된다.

 

 

소스코드

#include <iostream>
#include <cstring>
#include <vector>

typedef long long ll;
using namespace std;

int not_prime[2000001]; // 소수이면 0, 소수가 아니면 1

void sieve(){ //빠른 소수 판정을 위해 에라토스테네스의 체를 이용한 전처리를 해주는 함수
    for(int i=2; i<2000001; i++){
        if(not_prime[i]==0){
            for(int j=2*i; j<2000001; j+=i){
                not_prime[j]=1;
            }
        }
    }
}

int palindrome(int n){ //주어진 수가 팰린드롬인지 확인하는 함수
    string s=to_string(n);
    for(int i=0; i<s.length()/2; i++){
        if(s[i]!=s[s.length()-i-1]) return 0;
    }
    return 1;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    not_prime[0]=not_prime[1]=1; //초기화 유의할 것!!
    sieve();
    int n; cin>>n;
    while(1){
        if(!not_prime[n] && palindrome(n)){
            cout<<n;
            break;
        }
        n++;
    }
    return 0;
}