AtCoder Beginner Contest 099 C – Strange Bank をPython3で解く

# AtCoder Beginner Contest 099 C - Strange Bank
# https://atcoder.jp/contests/abc099/tasks/abc099_c
# tag: N進数

# 6 進数と 9 進数の組み合わせを考える問題。
# 幸い 1 <= N <= 100000 と制約が緩いので、
# 6 進数で数える分と 9 進数で数える分をわけることにして、全探索する。

def main():
    N = int(input())

    # ある数 x を p 進法で考えたときの
    # 各桁の数字の合計を返す関数を作成しておく。
    def get_op_num(x, p):
        result = 0
        while x:
            result += x % p
            x //= p
        return result

    result = N
    # 9 進法で数える分を 0 ～ N の範囲で動かし、全探索を行う。
    # 1 円の桁はどちらで数えても同じなので、9 の倍数だけ調べていく。
    for p_nine in range(0, N+1, 9):
        tmp = get_op_num(p_nine, 9) + get_op_num(N - p_nine, 6)
        if result > tmp:
            result = tmp
    
    print(result)

main()

# メモ化再帰を用いた場合
import sys
sys.setrecursionlimit(10**9)
def main():
    N = int(input())

    # dpt[x]: x 円を引き出すために必要な最小回数
    dpt = [-1] * (N+1)
    dpt[0] = 0

    def get_min_op(x):
        # メモがあればそれを返す。
        if dpt[x] != -1:
            return dpt[x]
        
        # 最大は x 回
        result = x

        # 1 円を引き出す場合
        tmp_r = get_min_op(x - 1) + 1
        if result > tmp_r:
            result = tmp_r

        # 9^n 円を引き出す場合
        prev = 9
        while prev <= x:
            tmp_r = get_min_op(x - prev) + 1
            if result > tmp_r:
                result = tmp_r
            prev *= 9

        # 6^n 円を引き出す場合
        prev = 6
        while prev <= x:
            tmp_r = get_min_op(x - prev) + 1
            if result > tmp_r:
                result = tmp_r
            prev *= 6
        
        dpt[x] = result
        return result

    result = get_min_op(N)
    print(result)
main()