PythonでJOI難易度5を埋める #11

C - 桁和 (Digit Sum)

考えたこと
N以下の全ての自然数を試そうとすると、きつそうなので別の方法を考えます。
考え方を逆にして、Nから1までの整数を調べてみることにします。を操作してNにできるなら、操作してiにできるような整数もNになります。(j→i→N)
このことから、Nから順に見ていって配列に追加していきます。listを使うと要素の検索にO(N)かかるので、setを使います。

n = int(input())

def digit_sum(n):
    ans = 0
    while n > 0:
        ans += n % 10
        n //= 10

    return ans

n_t = set()

for i in reversed(range(1, n+1)):
    if i == n:
        n_t.add(i)
    elif i + digit_sum(i) in n_t:
        n_t.add(i)

print(len(n_t))

i == nのとき、n_ t = {n}

i == 一回の操作でnになる。n_t = {n, i}

i == 一回の操作でiになる。n_t = {n, i, j}

となる。
参考にした記事