ABC099 C - Strange Bank

備忘録

問題

atcoder.jp

回答

import sys
import os


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = int(sys.stdin.readline().rstrip())

    ret = N
    for n in range(N+1):
        cnt = 0
        i = n

        while (i > 0):
            cnt += i % 6
            i //= 6

        j = N - n
        while (j > 0):
            cnt += j % 9
            j //= 9

        ret = min(cnt, ret)

    print(ret)


if __name__ == '__main__':
    main()

考え方

あまり理解できていない。。
整数Nを1から順に、6の累乗で引き出せるか否か探索し、
残りを9の累乗で引き出せるか否かを探索している？

        while (i > 0):
            cnt += i % 6
            i //= 6

上記箇所は
cnt += i % 6が6の余剰なので、1円を何回使用するか、
i //= 6が6の商（切り下げ）なので、6の累乗についての算出

whileでループすることで、先に1円使用分を抜き出し、
商（切り下げ）で6の累乗の最小回数を算出している？

後半の9についても同様の処理