[PS] 백준 30446번: 회문수

속으로 '되게 어려운데 이게 왜 실버지' 하고 꾸역꾸역 풀어서 맞췄다.

523456789의 숫자가 나오면

우선

1~9 : 9개

10~99 : 9개

100~999 : 90개

...

이런식으로 다 더해서 99999999까지 다 처리해두고

100000000부터 523456789까지를 셈한다

그럼 여기서도

100000000부터 499999999까지는 4 * 90000 / 9이니 이만큼 더해주고

이런식으로 가운데숫자(홀수면 한자리, 짝수면 두자리)만 제외하고 남기고 다 처리해준다.

 

5234 5 6789.

왼쪽을 뒤집은 4325보다 오른쪽의 6789가 더 크면 추가로 5를 더해주고

만약 숫자가 523453215라

5234 5 3215 이렇게 오른쪽이 더 작으면 추가로 4만 더해준다...

 

암튼 이런식으로 꾸역꾸역 해서 맞췄는데, 다른사람 답들을 보니 그냥 펠린드럼 수를 전부 다 만들어서 큰지 작은지만 봐주면 끝이였다.

 

생각해보면 진짜 펠린드럼수가 최대 199998개인데 이 199998개만 전부 검사해보면 되는것 아닌가.

왜 이생각을 못했을까...

 

숫자로 푼 버전

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define FOR(i, N) for (int i = 0; i < static_cast<long long>(N); i++)
#define FORL(e, S) for (auto& e : S)

long long n_max[10] = { 9, 9, 90, 90, 900, 900, 9000, 9000, 90000, 90000 };

int main() {
	long long n; cin >> n;
	int k = log10(n);

	long long ans = 0;
	FOR(i, k) ans += n_max[i];

	int cnt = 0;
	FOR(i, k / 2 + 1) {
		int left = (n / static_cast<long long>(pow(10, k - cnt))) % 10;
		int right = (n / static_cast<long long>(pow(10, cnt))) % 10;

		if (i == k / 2) {
			long long a = 0, b = 0;
			FOR(j, k / 2) {
				a = ((n / static_cast<long long>((pow(10, k - j)))) % 10) * static_cast<long long>(pow(10, j)) + a;
				b = b * 10 + (n / static_cast<long long>((pow(10, k / 2 - j - 1)))) % 10;
			}
			if (k < 2) {
				if (left > right) ans += (left - 1);
				else ans += left;
			}
			else {
				if (k % 2 == 0) {
					if (a > b) ans += left;
					else ans += (left + 1);
				}
				else {
					int twoval = 10 * left + right;
					if (b >= a) { for (int i = 0; i * 10 + i <= twoval; i++) ans++; }
					else { for (int i = 0; i * 10 + i < twoval; i++) ans++; }
				}
			}
			break;
		}
		if (cnt == 0) left -= 1;
		ans += left * n_max[k - 2 * cnt] / 9;
		cnt += 1;
	}

	cout << ans << endl;
}

 

펠린드럼 하나하나 만들어 푼 버전

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define FOR(i, N) for (int i = 0; i < int(N); i++)
#define FORL(e, S) for (auto& e : S)

#define ll long long

ll odd(int num, int btw) {
	string left = to_string(num);
	string mid = to_string(btw);
	string right = left;
	reverse(right.begin(), right.end());
	return stoll(left + mid + right);
}

ll even(int num) {
	string left = to_string(num);
	string right = left;
	reverse(right.begin(), right.end());
	return stoll(left + right);
}

int main() {
	long long n; cin >> n;
	int ans = 0;

	for (int i = 1; i < 10; i++) if (i <= n) ans++;

	for (int i = 1; i < 10000; i++)
		FOR(j, 10)
			if (odd(i, j) <= n) ans++;

	for (int i = 1; i < 100000; i++)
		if (even(i) <= n) ans++;

	cout << ans << endl;
}