[C++] 회문수 (백준 30446번)

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

 

#include <iostream>
#include <vector>
#include <string>
using namespace std;

long long n;
int posn, endn;
long long ans = 0;
bool fin = false;
string res = "";

void dfs(int idx) {
    if (fin) return;
    if (idx == endn) {
        if (stoll(res) <= n) {
            ans++;
        } else {
            fin = true;
        }
        return;
    }
    if (idx == 0) {
        for (int i = 1; i < 10; i++) {
            res[idx] = res[posn - idx - 1] = i + '0';
            dfs(idx + 1);
            if (fin) return;
        }
    } else {
        for (int i = 0; i < 10; i++) {
            res[idx] = res[posn - idx - 1] = i + '0';
            dfs(idx + 1);
            if (fin) return;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    posn = to_string(n).size();

    for (int i = 1; i < posn; i++) {
        long long tmp = 9;
        int endt = (i + 1) / 2;
        for (int j = 1; j < endt; j++) tmp *= 10;
        ans += tmp;
    }

    endn = (posn + 1) / 2;
    res.resize(posn, '0');

    dfs(0);

    cout << ans << '\n';
}

n보다 자릿수가 작은 회문수들을 카운트할 때는 9 * 10 * 10 ... 이런식으로 빠르게 구하고 (맨앞이 9인 이유는 맨 앞에는 0이 나올 수 없기 때문이다.) n과 자릿수가 같은 회문수들을 카운트할 때는 dfs를 통해 전체 탐색을 하면서 n보다 큰 수를 만나게 되면 종료하도록 하였다. (AC)