[C++] 백준 1747: 소수&팰린드롬

문제

[C++] 백준 1747: 소수&팰린드롬 SILVER 1
https://www.acmicpc.net/problem/1747

 

---

 

접근 방법

이 문제는 주어진 수 N 이상에서 가장 작은 소수이면서 팰린드롬(회문)인 수를 찾는 문제다.

즉, 두 조건을 동시에 만족해야 한다.

1. 소수(Prime Number)
2. 앞뒤가 같은 수(팰린드롬)

그래서 풀이를 두 단계로 나누었다.

 

1. 소수 판별 – 에라토스테네스의 체

먼저 충분히 큰 범위(약 1003000까지)에 대해
에라토스테네스의 체를 이용해 소수 여부를 미리 구해두었다.

for (int i = 2; i < vect.size(); i++)
{
    if (vect[i] != -1)
    {
        for (int j = i * 2; j < vect.size(); j += i)
        {
            vect[j] = -1;
        }
    }
}

• 소수가 아닌 수는 -1로 표시
• 마지막에 vect[0], vect[1]도 소수가 아니므로 -1 처리

이렇게 하면 이후에는 빠르게 소수 여부를 확인할 수 있다.

 

2. 팰린드롬 검사

N부터 시작해서 위에서 구한 소수 배열을 확인하면서 소수인 경우에만 팰린드롬 검사를 진행한다.

string str = to_string(vect[i]);
string rev = str;
reverse(rev.begin(), rev.end());

if (str == rev)

• 숫자를 문자열로 바꾼 뒤
• 뒤집은 문자열과 비교해서 같으면 팰린드롬

두 조건을 모두 만족하는 순간 바로 출력하고 종료한다.

 

구현 시 주의할 점

• 문제의 입력 범위 특성상, 소수를 매번 나눠보는 방식은 비효율적이므로 체를 먼저 구성하는 방식이 훨씬 빠르다.
• 팰린드롬 검사는 숫자 연산으로 구현해도 되지만, 문자열로 바꾸고 reverse()를 사용하는 방법이 간단하고 직관적이다.
• 소수 배열의 범위를 넉넉하게 잡아야 한다. (문제 조건상 1003000 정도면 충분)

 

 

---

 

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>  // reverse
using namespace std;

typedef long long LL;

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

	LL n = 0;
	cin >> n;

	vector<int> vect(1003002, 0);
	for (int i = 0; i < vect.size(); i++)
		vect[i] = i;
	for (int i = 2; i < vect.size(); i++)  // 에라토스테네스의 체
	{
		if (vect[i] != -1)
		{
			for (int j = i * 2; j < vect.size(); j += i)
			{
				vect[j] = -1;
			}
		}
	}
	vect[0] = -1;
	vect[1] = -1;
	for (LL i = n; i < vect.size(); i++)
	{
		if (vect[i] != -1)
		{
			string str = to_string(vect[i]);
			string rev = str;
			reverse(rev.begin(), rev.end());

			if (str == rev)
			{
				cout << vect[i];
				return 0;
			}
		}
	}

	return 0;
}