백준 30446번 (C++)
https://www.acmicpc.net/problem/30446
30446번: 회문수
어떤 양의 정수 $P$에 대해 $P$를 구성하는 숫자들을 왼쪽부터 적는 경우와 오른쪽부터 적은 결과가 서로 일치할 경우, $P$를 회문수(palindrome number)라 한다. 예를 들어 $1$, $101$, $12322321$은 모두 회문
www.acmicpc.net
ICPC 2023 예선에 나온 문제다. 당시에 G번을 붙잡고 있다가 이분탐색으로 풀 수 있겠다 싶었지만 최적화가 부족해 시간초과가 났고 30분 남은 상황에서 이 문제를 쳐다봤다. 하지만 멘탈이 나간 상황이라 풀지 못했다. 지금 다시 풀어보니 간단한 문제였다.
10^10이하의 숫자 N이 입력되면 1부터 N까지 숫자 중에 회문수가 몇 개인지 세는 문제다.
무지성 구현을 하고 제출해보니 당연하게도 시간초과가 났다.
어떻게 해야 시간을 줄일 수 있을까?
위의 무지성 코드에서 시간 초과가 난 이유는 단순하다.
1부터 10^10까지 회문수가 아닌 수가 훨씬 많은데 모든 숫자를 일일이 회문수인지 탐색했기 때문이다.
따라서 회문수만 생성하여 N보다 작거나 같은 경우만 카운트하면 된다.
회문수는 숫자를 반으로 가르고 왼쪽과 오른쪽을 비교했을 때 같으면 된다.
123456 이라는 숫자를 입력 받았다고 가정해보자.
숫자를 반으로 자르고 앞부분(123)만 기억한다.
앞부분을 복사하고 반전시킨 뒤 이어 붙이면 회문수가 완성된다.
그리고 완성된 회문수가 N보다 작거나 같은지만 확인해 주면 된다.
이 과정을 앞부분(123)이 0이 될때까지 반복하면 끝이다.
짧게나마 과정을 작성해보면
123 -> 123321
122 -> 122221
121 -> 121121
.
.
.
1 -> 11
이렇게 회문수만 생성할 수 있다.
여기서 첫 번째 문제점이 있다. 한 자리수는 무조건 회문수인데 위의 방법으로는 구할 수 없다.
해결 방법은 그냥 따로 더해주면 된다.
두 번째 문제점이다.
예를 들어보자. 123456 이라는 숫자를 입력 받아서 123부터 회문수를 생성한다.
123, 122, 121, ..., 100까지 생성하고 나면 다음은 99인데 100까지는 회문수를 생성하면 100001으로 6자리 숫자가 나온다.
하지만 99는 9999로 4자리 숫자가 나오게 된다. 즉, 5자리(홀수) 숫자는 생성하지 못한다는 것이다.
따라서 앞부분 + 뒷부분으로만 회문수를 생성하는 게 아니라 앞부분 + 0~9 + 뒷부분으로 회문수를 따로 생성해 줘야 한다.
N보다 작거나 같은 경우만 카운트하기 때문에 입력된 값보다 길이가 커지는 경우는 고려하지 않아도 된다.
다음은 C++로 작성된 코드다.
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <deque>
#include <cmath>
#include <memory.h>
#include <stack>
#include <map>
#include <set>
#include <numeric>
#define X first
#define Y second
#define INF 0x3f3f3f3f
#define MOD 998244353
#define ll long long
#define int long long
#define pi pair<int,int>
using namespace std;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int n, ans = 0;
cin >> n;
int tmp = n;
string s = to_string(n);
for (int i = 0; i < s.size() / 2; i++)
tmp /= 10;
while (tmp)
{
string l = to_string(tmp);
string r = l;
reverse(r.begin(), r.end());
string value = l + r;
int num = stoll(value);
if (num <= n)
ans++;
for (int i = 0; i < 10; i++)
{
string value2 = "";
value2 += l;
value2 += i + 48;
value2 += r;
int num2 = stoll(value2);
if (num2 <= n)
ans++;
}
tmp--;
}
if (n >= 9)
ans += 9;
else
ans += n;
cout << ans << '\n';
}