2025 SCPC 3-1

1
#include <iostream>
2
#include <string>
3
#include <unordered_map>
4
using namespace std;
5

6
string N;
7
unordered_map<string, long long> memo;
8

9
// key 생성 함수
10
string make_key(int pos, bool tight, bool leading_zero) {
11
    return to_string(pos) + "_" + to_string(tight) + "_" + to_string(leading_zero);
12
}
13

14
long long dfs(int pos, bool tight, bool leading_zero) {
15
    if (pos == N.size()) return leading_zero ? 0 : 1;
16

17
    string key = make_key(pos, tight, leading_zero);
18
    if (memo.count(key)) return memo[key];
19

20
    char limit = tight ? N[pos] : '2';
21
    long long res = 0;
22

23
    for (char d : {'0', '1', '2'}) {
24
        if (tight && d > limit) continue;
25
        if (leading_zero && d == '0' && pos == 0) continue;
26

27
        bool next_tight = tight && (d == limit);
28
        bool next_leading_zero = leading_zero && (d == '0');
29

30
        res += dfs(pos + 1, next_tight, next_leading_zero);
31
    }
32

33
    return memo[key] = res;
34
}
35

36
long long count_valid(const string& num) {
37
    N = num;
38
    memo.clear();
39
    return dfs(0, true, true);
40
}