[BOJ] 백준 1990. 소수인팰린드롬 (Gold V)

학교 채점현황을 둘러보다가 발견한 문제.

문제는 아래와 같다.

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

1990번: 소수인팰린드롬

---

의식의 흐름 및 해설

소수 문제인데 팰린드롬이어야 하는 문제이다.

범위가 1억까지이기 때문에 애매하게 시간초과가 될까말까한 문제처럼 보였는데,

생각해보니 팰린드롬인지 체크해주는 과정 때문에 O(1억 * s.length())이므로 시간초과가 나오기 충분한 시간복잡도였다.

특히, 수가 클수록 수가 많으므로 (ex.10 ~100 까진 90개, 천만~1억까진 9천만개) 최악에 가까운 시간복잡도가 나온다.

조금 최적화가 필요해보였다.

 

팰린드롬 수 중에서 소수를 체크해주는 방법으로 방향을 틀어보았다.

팰린드롬 수를 어떻게 체크할까... 어차피 원래 수+reverse(원래수) pow(10, length)+reverse(원래수)를 하면 팰린드롬 수니까 bfs로 구할까... 생각을 하다가 한가지 생각이 났다.

짝수 팰린드롬 수 용어가 실제로 있는진 모르겠다. 그냥 4자리 수, 6자리 수와 같은 자릿수가 짝수인 팰린드롬 수를 의미한다.

바로 짝수 팰린드롬 수는 11의 배수이기 때문에 11을 제외하고는 소수가 될 수 없다는 점이다!

이 점을 이용하면 시간초과를 겪지 않고 풀 수 있다.

 

나의 경우는 어차피 짝수팰린드롬수는 11을 제외하곤 소수가 될 수 없으므로 1~sqrt(B)의 숫자 N을 문자열로 형변환한 후 N+(0~9)+reverse(N) 을 한 홀수팰린드롬수 중에서 소수인지 체크해주었다.

 

시간복잡도는 대략 위와 같으나, reverse, == 연산 등을 고려하면 좀 더 시간이 걸릴 것이다.

확실한건 충분한 최적화가 이루어졌다는 점이다.

---

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b;
vector<ll> v;
bool check(ll n){
	for(ll i=2;i*i<=n;i++){
		if(!(n%i))
		    return false;
	}
	return true;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin>>a>>b;
	for(ll i=a;i<=min(b, 1LL*11);i++){
		if(check(i))
		    v.push_back(i);
	}
	for(int i=1;i*i<=b;i++){
		string s=to_string(i);
		string rev=s;
		reverse(rev.begin(), rev.end());
		for(int j=0;j<10;j++){
			string str=s+to_string(j)+rev;
			ll n=stoll(str);
			if(n<a||n>b)
			    continue;
			if(check(n))
			    v.push_back(n);
		}
	}
	v.push_back(-1);
	for(auto i: v)
	    cout<<i<<"\n";
}

폰으로 풀면 ideone으로 풀기 때문에 가독성이 좀 떨어진다.

---

정수론적 성질을 이용해야 하는 꽤 재밌는 문제였다.

맞추고보니 G5였는데, G5는 너무 낮은 듯해서 G4에 투표하였다.