이 튜토리얼에서는 회문(palindrome)의 제곱에 해당하는 수, 즉 슈퍼 팰린드롬(Super Palindrome)의 개수를 구하는 프로그램을 다룹니다.
두 값 L과 R이 주어졌을 때, 해당 범위 내에 존재하는 슈퍼 팰린드롬의 개수를 찾는 것이 목표입니다. 여기서 슈퍼 팰린드롬이란 숫자 자신과 그 숫자의 제곱이 모두 회문인 수를 의미합니다. 예를 들어 121은 회문이고, 그 제곱근인 11 역시 회문이므로 슈퍼 팰린드롬입니다.
접근 방법
모든 회문은 앞부분 절반을 뒤집어 뒤에 붙이는 방식으로 생성할 수 있습니다. 이 성질을 활용해 홀수 길이 회문과 짝수 길이 회문을 각각 만든 뒤, 그 제곱값이 범위 [L, R] 안에 속하면서 동시에 회문인지 검사하면 됩니다. 생성되는 회문은 인덱스가 커질수록 단조 증가하므로, 제곱값이 R을 초과하는 시점에 반복을 종료해도 누락 없이 탐색할 수 있습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
//checking if the number is a palindrome
bool if_palin(int x){
int ans = 0;
int temp = x;
while (temp > 0){
ans = 10 * ans + temp % 10;
temp = temp / 10;
}
return ans == x;
}
//returning the count of palindrome
int is_spalin(int L, int R){
// Upper limit
int LIMIT = 100000;
int ans = 0;
for (int i = 0 ;i < LIMIT; i++){
string s = to_string(i);
string rs = s.substr(0, s.size() - 1);
reverse(rs.begin(), rs.end());
string p = s + rs;
int p_sq = pow(stoi(p), 2);
if (p_sq > R)
break;
if (p_sq >= L and if_palin(p_sq))
ans = ans + 1;
}
//counting even length palindromes
for (int i = 0 ;i < LIMIT; i++){
string s = to_string(i);
string rs = s;
reverse(rs.begin(), rs.end());
string p = s + rs;
int p_sq = pow(stoi(p), 2);
if (p_sq > R)
break;
if (p_sq >= L and if_palin(p_sq))
ans = ans + 1;
}
return ans;
}
int main(){
string L = "4";
string R = "1000";
printf("%d\n", is_spalin(stoi(L), stoi(R)));
return 0;
}출력 결과
4
코드 설명
if_palin() 함수는 숫자의 자릿수를 역순으로 조합해 원래 값과 비교함으로써 회문 여부를 판별합니다.
is_spalin() 함수는 두 단계로 나뉘어 동작합니다.
- 첫 번째 반복문(홀수 길이): 문자열에서 마지막 한 글자를 제외한 나머지를 뒤집어 뒤에 붙여 홀수 길이 회문을 생성합니다. 예를 들어 "12" → "121".
- 두 번째 반복문(짝수 길이): 문자열 전체를 그대로 뒤집어 붙여 짝수 길이 회문을 생성합니다. 예를 들어 "12" → "1221".
생성된 회문 p의 제곱이 R보다 크면 이후 값들은 모두 범위를 벗어나므로 반복을 중단하고, 제곱값이 L 이상이면서 회문인 경우에만 카운트를 증가시킵니다.
결과 분석
L = 4, R = 1000일 때 출력은 4입니다. 이는 해당 범위 내 슈퍼 팰린드롬이 정확히 네 개, 즉 4(2²), 9(3²), 121(11²), 484(22²)이기 때문입니다. 참고로 676(26²)처럼 제곱근이 회문이 아닌 수는 슈퍼 팰린드롬에서 제외됩니다.