Problem:


Score : 300 points

Problem Statement

To make it difficult to withdraw money, a certain bank allows its customers to withdraw only one of the following amounts in one operation:

1 yen (the currency of Japan)

6 yen, 6^2(=36) yen, 6^3(=216) yen, ...

9 yen, 9^2(=81) yen, 9^3(=729) yen, ...

At least how many operations are required to withdraw exactly N yen in total?

It is not allowed to re-deposit the money you withdrew.

Constraints

1 \leq N \leq 100000

N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

If at least x operations are required to withdraw exactly N yen in total, print x.

Sample Input 1

127

Sample Output 1

4

By withdrawing 1 yen, 9 yen, 36(=6^2) yen and 81(=9^2) yen, we can withdraw 127 yen in four operations.

Sample Input 2

3

Sample Output 2

3

By withdrawing 1 yen three times, we can withdraw 3 yen in three operations.

Sample Input 3

44852

Sample Output 3

16



Sample input:
127


Sample output:
4

Submission status: Accepted

Solution code:
a=int(input())
dp=[float('inf') for i in range(100000+10)]
dp[0]=0
for i in range(1,100000+1):
    dp[i]=dp[i-1]+1
    for k in [6,9]:
        for j in range(1,7):
            if k**j <=i :
                dp[i]=min(dp[i],dp[i-k**j]+1)
print(dp[a])

Submission status: Accepted

Solution code:
import math

def A():
    x, a, b = [int(x) for x in input().split()]
    if abs(x-a) < abs(x-b):
        print('A')
    else:
        print('B')
def B():
    S = input()
    alphabet = [False for x in range(26)]
    for char in S:
        i = ord(char) - ord('a')
        alphabet[i] = True
    printed = False
    for i in range(len(alphabet)):
        if alphabet[i] == False:
            print(chr(ord('a')+i))
            printed = True
            break
    if printed == False:
        print("None")
def C():
    num = sorted([1] + [pow(6, x+1) for x in range(6)] + [pow(9, x+1) for x in range(5)])
    n = int(input())
    stack = [(n, 0)]
    memo = {}
    _min = 999999

    cost = {}

    while len(stack) > 0:
        node = stack.pop()
        for k in num:
            if node[0] >= k:
                ans = (node[0] - k, node[1] + 1)
                if ans[0] == 0:
                    _min = min(_min, ans[1])
                else:
                    if str(ans[0]) in memo and memo[str(ans[0])] <= ans[1]:
                        pass
                    else:
                        stack.append(ans)
                        memo[str(ans[0])] = ans[1]
    print(_min)

def E():
    n, m = [int(x) for x in input().split()]
    P = [[] for i in range(n)]
    for j in range(m):
        p, y = [int(x) for x in input().split()]
        P[p-1].append([y, ('000000'+str(p))[-6:], j])

    for i in range(n):
        P[i] = sorted(P[i], key=lambda x:x[0])
        for j in range(len(P[i])):
            P[i][j][1] += (('000000'+str(j+1))[-6:])
    P = [e for inner_list in P for e in inner_list]
    P = sorted(P, key=lambda x:x[2])
    for p in P:
        print(p[1])
C()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n = II()
    dp = [inf for i in range(n + 1)]
    ans = [1]
    x = 6
    while x <= n:
        ans.append(x)
        x = x * 6
    x = 9
    while x <= n:
        ans.append(x)
        x = x * 9
    ans.sort()
    for i in ans:
        dp[i] = 1
    for i in range(1, n + 1):
        if not i in ans:
            a = bisect.bisect_left(ans, i)
            for k in range(a):
                #print(i,ans[k], a)
                dp[i] = min(dp[i - ans[k]] + 1, dp[i])
    print(dp[n])

    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    C()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n = I()
    ans = float("inf")
    for i in range(n+1):
        m = 0
        k = i
        while k > 0:
            m += k%6
            k //= 6
        k = n-i
        while k > 0:
            m += k%9
            k //= 9
        ans = min(ans,m)
    print(ans)
#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    C()

Submission status: Accepted

Solution code:
# もらうDP
N = int(input())
dp = {}
for n in range(N+1):
    if n == 0:
        dp[0] = 0
    else:
        res = n
        pow6 = 1
        while n - pow6 >= 0:
            res = min(res, dp[n-pow6] +1)
            pow6 *= 6
        pow9 = 1
        while n -pow9 >= 0:
            res = min(res, dp[n-pow9] +1)
            pow9 *= 9
        dp[n] = res
print(dp[N])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6) 

def memorize(f):
    table = {}
    def func(*args):
        if not args in table:
            table[args] = f(*args)
        return table[args]
    return func

@memorize
def memDFS(n):
    if n==0:
        return 0
    else:
        res = n
        pow6 = 1
        while(pow6<=n):
            res = min(res, memDFS(n-pow6)+1)
            pow6 *= 6
        pow9 = 1
        while(pow9<=n):
            res = min(res, memDFS(n-pow9)+1)
            pow9 *= 9
        return res

N = int(input())
print(memDFS(N))

Submission status: Accepted

Solution code:
n=int(input())
dp=[i for i in range(n+1)]
lw=[6,9]
for w in lw:
    k=1
    while w**k<=n:
        q=w**k
        for j in range(n+1-q):
            dp[j+q]=min(dp[j]+1,dp[j+q])
        k+=1
print(dp[n])

Submission status: Accepted

Solution code:
N = int(input())
dp = [N] * (N+1)
dp[0] = 0

for i in range(1, N+1):
    pow6 = []
    pow9 = []
    for j in range(i):
        if 6**j > i:
            break
        pow6.append(6**j)
    for k in range(i):
        if 9**k > i:
            break
        pow9.append(9**k)
    L = set(pow6 + pow9)
    
    for l in L:
        if i-l < 0:
            break
        dp[i] = min(dp[i], dp[i-l]+1)

print(dp[N])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

def rec(n):
    if n == 0:
        memo[n] = 0
        return memo[n]
    if memo[n] != -1:
        return memo[n]
    res = n
    pow6 = []
    pow9 = []
    for i in range(n):
        if 6 ** i > n:
            break
        pow6.append(6 ** i)
    
    for j in range(1, n):
        if 9 ** j > n:
            break
        pow9.append(9 ** j)
    L = set(pow6 + pow9)
    
    for k in L:
        res = min(res, rec(n - k)+1)
        
    memo[n] = res
    return memo[n]
    

N = int(input())
memo = [-1] * (N+1)
print(rec(N))

Submission status: Accepted

Solution code:
def read():
    return raw_input()


def write(message):
    import sys
    print message
    sys.stdout.flush()


if __name__ == '__main__':
    n = int(read())

    allowed = [1, ]
    spow = 6
    while spow <= n:
        allowed.append(spow)
        spow *= 6
    npow = 9
    while npow <= n:
        allowed.append(npow)
        npow *= 9

    allowed = allowed[::-1]
    res = {a: 1 for a in allowed}

    def min_ops(N):
        global res
        global allowed
        if N in res:
            return res[N]

        for a in allowed:
            if N - a > 0:
                if N not in res or min_ops(N-a) + 1 < res[N]:
                    res[N] = min_ops(N-a) + 1
        return res[N]

    write(min_ops(n))

Submission status: Accepted

Solution code:
N = int(input())
MAX_N = 100000
dp = [MAX_N for _ in range(N + 1)]
# 1円は無視していい。9**a, 6**b だけでどこまでNに近づけるかが勝負
# N - nearest が1円の数
dp[0] = 0
for num in [6, 9]:
    for i in range(N):
        if dp[i] == MAX_N:
            continue
        for j in range(1, 7): #6**7 で10万(MAX_N)を突破する
            idx = i + pow(num, j)
            if idx > N:
                break
            dp[idx] = min(dp[idx], dp[i] + 1)

# dpを逆からあさり、初期値でない場所を見る
min_cost = MAX_N
min_idx = max(-1, N - 1000) #1000個もあされば十分。たぶん10でもいい
for i in range(N, min_idx, -1):
    if dp[i] < MAX_N:
        remain = N - i
        cost = remain + dp[i]
        if min_cost > cost:
            min_cost = cost
print(min_cost)

Submission status: Accepted

Solution code:
N = int(input())
sixes = [6 ** i for i in range(1, 7)]
nines = [9 ** i for i in range(1, 6)]
coin = [1] + sixes + nines
INF = 10**6
dp = [INF] * 100010
dp[0] = 0  # dp[i]:i円引き出すのに必要な回数
for money in range(1, N + 1):
    dp[money] = min([dp[money-i] + 1 for i in coin if i <= money])
print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())
# DPだと思ったけど、2次元じゃなくて1次元だった
# けんちょんさん曰く、1次元でできないときに2次元で考える
sixes = [6 ** i for i in range(1, 7)]
nines = [9 ** i for i in range(1, 6)]
coin = [1] + sixes + nines
INF = 10**6
dp = [INF] * 100010
dp[0] = 0  # dp[i]:i円引き出すのに必要な回数
for money in range(1, N + 1):
    dp_candidate = []
    for coin_ in coin:
        if money < coin_:
            continue
        else:
            dp_candidate.append(dp[money-coin_] + 1)
    dp[money] = min(dp_candidate)
print(dp[N])

Submission status: Accepted

Solution code:
n = int(input())

coins = [9**5,6**6,6**5,9**4,6**4,9**3,6**3,9**2,6**2,9,6,1]

res = n

dp = [-1]*(n+1)
dp[0] = 0
min_coins = [-1]*(n+1)
for i in range(1,n+1):
    min_c = n+1 
    c = 0
    for coin in coins:
        if coin <= i:
            #find first coin no more than i
            if dp[i-coin] != -1 and 1 + dp[i-coin]<min_c:
                min_c = 1+dp[i-coin]
                c = coin
    if min_c == n+1:
        dp[i] = -1
    else:
        dp[i] = min_c
        min_coins[i] = c
print(dp[n])
'''
money = n
for i in range(dp[n]):
    print(min_coins[money])
    money-=min_coins[money]
'''

Submission status: Accepted

Solution code:

n = int(input())
pre_list = [1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
 
#nをn+1個並べたリストを作る
dp = [n]*(n+1)
#0を初期化する
dp[0] = 0
 
 
#dp[i]について一つずつ考える
for i in range(1,n+1):
#dp[i]のそれぞれの場合分けについて考える。場合はpre_listの中身の分だけ回せばいい
	for j in pre_list:
		if i - j >= 0:
			dp[i] = min(dp[i],dp[i-j]+1)
 
print(dp[n])

Submission status: Accepted

Solution code:
n = int(input())
dp = [n] * (n + 1)
dp[0] = 0
a = [1, 6**1, 6**2, 6**3, 6**4, 6**5, 6**6, 9**1, 9**2, 9**3, 9**4, 9**5]
for i in range(1, n + 1):
    for j in a:
        if i - j >= 0:
            dp[i] = min(dp[i], dp[i - j] + 1)
print(dp[n])

Submission status: Accepted

Solution code:
n = int(input())

pre_list=[1, 6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049]
dp = [-1]*(n+1)
dp[0] = 0
dp[1] = 1

for i in range(2,n+1):
    a = []
    a.append(dp[i-1]+1)
    for j in pre_list:
        if i-j >= 0:
            a.append(dp[i-j]+1)
        else:
            break

    dp[i] = min(a)

print(dp[-1])

Submission status: Accepted

Solution code:
from math import ceil, log


def solve(string):
    n = int(string)
    max_number = 10**5
    can_operate = [1] + [6**(i + 1) for i in range(ceil(log(max_number, 6)))
                        ] + [9**(i + 1) for i in range(ceil(log(max_number, 9)))]
    can_operate = sorted(can_operate)
    dp = [0]
    for _ in range(n + 0):
        tmp = n
        for o in can_operate:
            index = len(dp) - o
            if index < 0:
                break
            tmp = min(tmp, dp[index] + 1)
        dp.append(tmp)
    return str(dp[-1])


if __name__ == '__main__':
    print(solve(input()))

Submission status: Accepted

Solution code:
N = int(input())


def main():
    ans = N

    for i in range(N + 1):
        num = 0
        cur = i

        while 0 < cur:
            num += cur % 6
            cur //= 6

        cur = N - i

        while 0 < cur:
            num += cur % 9
            cur //= 9

        if num < ans:
            ans = num

    print(ans)
    return


main()

Submission status: Accepted

Solution code:
N = int(input())
dp = [0]
six = 0
nine = 0
co = 0
for i in range(N+1):
    if i % (6**(six)) == 0:
        if 6**six > 9**nine:
            co = i
        six += 1
    if i % (9**(nine)) == 0:
        if 6**six < 9**nine:
            co = i
        nine += 1
    if i == 0:
        continue
    dpi = min(dp[i-1],dp[i-6**(six-1)],dp[i-9**(nine-1)])
    dp.append(dpi+1)
print(dp[N])

Submission status: Accepted

Solution code:
N=int(input())
res=N
for i in range(N+1):
    cc=0
    tmp=i
    while tmp>0:
        cc+=tmp%6
        tmp=tmp//6
    tmp=N-i
    while tmp>0:
        cc+=tmp%9
        tmp=tmp//9
    res=min(res,cc)
print(res)

Submission status: Accepted

Solution code:
N=int(input())
weights=[1]
pow6=6
while N>=pow6:
    weights.append(pow6)
    pow6*=6
pow9=9
while N>=pow9:
    weights.append(pow9)
    pow9*=9
dp=[1<<28]*(N+1)
dp[0]=0
for i in range(len(weights)):
    for j in range(weights[i],N+1):
        dp[j]=min(dp[j],dp[j-weights[i]]+1)
print(dp[N])

Submission status: Accepted

Solution code:
n=int(input())
ans=10**9
for i in range(n+1):
    tmp=i
    res=0
    while tmp:
        res+=tmp%6
        tmp//=6
    tmp=n-i
    while tmp:
        res+=tmp%9
        tmp//=9
    ans=min(ans, res)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
dp=[N]*(N+1)
dp[0]=0
for i in range(N):
    pow6=1
    while i+pow6<=N:
        dp[i+pow6]=min(dp[i+pow6],dp[i]+1)
        pow6*=6
    pow9=1
    while i+pow9<=N:
        dp[i+pow9]=min(dp[i+pow9],dp[i]+1)
        pow9*=9
print(dp[N])

Submission status: Accepted

Solution code:
N=int(input())
dp=[N]*(N+1)
dp[0]=0
for i in range(1,N+1):
    dp[i]=min(dp[i],dp[i-1]+1)
    pow6 = 1
    while i>=pow6:
        dp[i]=min(dp[i],dp[i-pow6]+1)
        pow6*=6
    pow9 = 1
    while i>=pow9:
        dp[i]=min(dp[i],dp[i-pow9]+1)
        pow9*=9
print(dp[N])

Submission status: Accepted

Solution code:
def strange_bank(N: int) -> int:
    prices = [1] + \
        [9 ** i for i in range(1, 6)] + \
        [6 ** i for i in range(1, 7)]
    dp = [float('inf')] * (N + 1)
    dp[N] = 0

    for n in range(N, 0, -1):
        for p in prices:
            if p <= N:
                dp[n-p] = min(dp[n] + 1, dp[n-p])

    return dp[0]


if __name__ == "__main__":
    N = int(input())
    ans = strange_bank(N)
    print(ans)

Submission status: Accepted

Solution code:
from itertools import count, takewhile
N = int(input())

def dfs(n, d={}):
  if(n < 6):
    return n
  if(n in d):
    return d[n]
  mn = max(takewhile(lambda x: x<=n, (9**i for i in count())))
  ms = max(takewhile(lambda x: x<=n, (6**i for i in count())))
  d[n] = min(dfs(n-mn), dfs(n-ms))+1
  return d[n]

print(dfs(N))

Submission status: Accepted

Solution code:
N = int(input())

ans = 1e9
for i in range(N+1):
  cnt = 0
  tmp = i
  while tmp > 0:
    cnt += tmp%6
    tmp //= 6
  tmp = N-i
  while tmp > 0:
    cnt += tmp%9
    tmp //= 9
  ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
import collections

c9 = []
c6 = []
for i in range(7):
    c9.append(9 ** i)
    c6.append(6 ** i)

inf = 1 << 60
N = int(input())
q = collections.deque()
q.append((N,0))
ans = inf
try:
    while True:
        v = q.popleft()
        if v[1] >= ans:
            continue
        for i in range(6,0,-1):
            if v[0] >= c9[i]:
                v2 = (v[0] - c9[i], v[1] + 1)
                q.append(v2)
                break
        for i in range(6,0,-1):
            if v[0] >= c6[i]:
                v2 = (v[0] - c6[i], v[1] + 1)
                q.append(v2)
                break
        if v[0] < 6:
            v2 = (0, v[1] + v[0])
            ans = min(ans, v2[1])

except IndexError:
    pass

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
all = [1]
all.extend([9 ** i for i in range(1, 6)])
all.extend([6 ** i for i in range(1, 7)])
all.sort()
INF = 10 ** 12
dp = [INF] * (N + 1)
dp[0] = 0
def func_dp(n, k):
    if n - k >= 0:
        return dp[n - k]
    return INF
for i in range(1, N + 1):
    dp[i] = 1 + min([func_dp(i, j) for j in all])
print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())
dp = [0]*100001
L = [1,6,36,216,1296,7776,46656,9,81,729,6561,59049]
for i in range(100001):
    for j in range(len(L)):
        if 1 <= i+L[j] <= 100000:
            if dp[i+L[j]] == 0:
                dp[i+L[j]] = dp[i]+1
            else:
                dp[i+L[j]] = min(dp[i]+1,dp[i+L[j]]) 
print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())
S = [1, 6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049]
X = [-1] * (N+1)
X[0] = 0
for i in range(1, N+1):
    mi = X[i-1] + 1
    for s in S:
        if s <= i:
            mi = min(mi, X[i-s] + 1)
    X[i] = mi

print(X[N])

Submission status: Accepted

Solution code:
n = int(input())
ws = [1]
ws += [6**i for i in range(1, 8)]
ws += [9**i for i in range(1, 6)]
ws = sorted(set(ws))

INF = 10**5
dp = [INF] * (n+1)
dp[0] = 0
for i in range(n+1):
    for w in ws:
        if i + w <= n:
            dp[i+w] = min(dp[i]+1, dp[i+w])
print(dp[-1])

Submission status: Accepted

Solution code:
N = int(input())
ans = N
for i in range(N+1):
    count = 0
    ret = i
    while ret > 0 :
        count += ret % 6
        ret //= 6
    ret = N - i
    while ret > 0 :
        count += ret % 9
        ret //= 9
    ans = min(ans, count)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
inf=10**5
dp=[inf]*(N+1)
dp[0]=0

sixes=[6**(i) for i in range(1,7)]
nines=[9**(i) for i in range(1,6)]

for i in range(1,N+1):
  dp[i]=dp[i-1]+1
  
  for s in sixes:
    if i-s>=0:
      dp[i]=min(dp[i],dp[i-s]+1)
    else:
      break
      
  for n in nines:
    if i-n>=0:
      dp[i]=min(dp[i],dp[i-n]+1)
    else:
      break

print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())
INF = 10 ** 9

dp = [0] * (N + 1)
for i in range(1, N + 1):
    tmp = INF
    p = 1
    while p <= i:
        tmp = min(tmp, 1 + dp[i - p])
        p *= 6
    p = 1
    while p <= i:
        tmp = min(tmp, 1 + dp[i - p])
        p *= 9
    dp[i] = tmp

print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())

nine = [9**i for i in range(7, 0, -1)]
six = [6**i for i in range(8, 0, -1)]
tmp = {}

def f(n):
  if(n < 6):
    return n
  if(n in tmp):
    return tmp[n]
  
  m = 1e9+7
  if(n >= 9):
    mn = max(x for x in nine if x <= n)
    if(n%mn == 0):
      m = min(m, n//mn)
    else:
      m = min(m, f(n-mn)+1)
  ms = max(x for x in six if x <= n)
  if(n%ms == 0):
    m = min(m, n//ms)
  tmp[n] = min(m, f(n-ms)+1)
  return tmp[n]
print(f(N))

Submission status: Accepted

Solution code:
n = int(input())
lis = [1, 6, 36, 216, 1296, 7776, 46656,9, 81, 729, 6561, 59049]
lis.sort(reverse=True)
dp = [10 ** 10 for i in range(n+1)]
dp[0] = 0
for i in range(n):
  for num in lis:
    try:
      dp[i+num] = min(dp[i+num],dp[i]+1)
    except:
      continue
print(dp[n])

Submission status: Accepted

Solution code:
n = int(input())
res = n

for i in range(n + 1):
  cc = 0
  t = i  # 6^pでi円引き出し
  while t > 0:
    cc += t % 6
    t //= 6
  t = n - i  # 9^pで残り引き出し
  while t > 0:
    cc += t % 9
    t //= 9
  if res > cc:
    res = cc
print(res)

Submission status: Accepted

Solution code:
N = int(input())

list_1 = [1]
list_6 = [6**(i+1) for i in range(6)]
list_9 = [9**(i+1) for i in range(5)]
list_169 = list_1+list_6+list_9

list_169 = sorted(list_169, reverse=True)


N_sub = N
d_count = 0
for i in range(len(list_169)):
    while list_169[i] <= N_sub:
        N_sub -= list_169[i]
        d_count += 1


dp = [[100000 for j in range(13)] for i in range(N+1)]

def N_mai(N_sub, index, s_count):
    global d_count
    if N_sub == 0:
        return 0
    elif dp[N_sub][index] != 100000:
        return dp[N_sub][index]
    else:
        if list_169[index] == 1:
            count = N_sub
        elif N_sub >= list_169[index]:
            count = min(N_mai(N_sub - list_169[index], index, s_count+1)+1,
                        N_mai(N_sub - list_169[index], index+1, s_count+1)+1, 
                        N_mai(N_sub, index+1, s_count))
        else:
            count = N_mai(N_sub, index+1, s_count)

        dp[N_sub][index] = count
        return count

print(min(d_count, N_mai(N, 0, 0)))

Submission status: Accepted

Solution code:
n = int(input())
amounts = [1, 6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049]

INF = 10 ** 6
dp = [INF] * (n + 1)
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
  for a in amounts:
    r = i - a
    if r >= 0:
      dp[i] = min(dp[i], dp[r] + 1)
print(dp[n])

Submission status: Accepted

Solution code:
a=int(input())
l=[i for i in range(a+1)]
i=1
while 6**i<=a:
    q=6**i
    for x in range(q,a+1):
        l[x]=min(l[x-q]+1,l[x])
    i+=1
i=1
while 9**i<=a:
    q=9**i
    for x in range(q,a+1):
        l[x]=min(l[x-q]+1,l[x])
    i+=1
print(l[a])

Submission status: Accepted

Solution code:
n = int(input())
c = [6**i for i in range(1,7)]
c.extend([9**i for i in range(1, 6)])
c = sorted(c)[::-1]
dp = [0]*1000000
for i in range(1,n+1):
    dp[i]=dp[i-1]+1
    for c_ in c:
        if i>=c_:
            dp[i]=min(dp[i],dp[i-c_]+1)
print(dp[n])

Submission status: Accepted

Solution code:
N = int(input())
inf = float("inf")
dp = [inf]*(100011)
def main():
    dp[0] = 0
    for i in range(1,100011):
        dp[i] = inf
        power_6 = 1
        power_9 = 1
        while power_6 <= i:
            dp[i] = min(dp[i],dp[i-power_6]+1)
            power_6 *= 6
        while power_9 <= i:
            dp[i] = min(dp[i],dp[i-power_9]+1)
            power_9 *= 9

if __name__ == "__main__":
    main()
    print(dp[N])

Submission status: Accepted

Solution code:
import sys
from itertools import count, takewhile

def dfs(n, d={}):
  if n < 6:
    return n
  if n in d:
    return d[n]

  max9 = max(takewhile(lambda x: x<=n, (9**i for i in count())))
  max6 = max(takewhile(lambda x: x<=n, (6**i for i in count())))
  d[n] = min(dfs(n-max9), dfs(n-max6)) + 1
  return d[n]


def main():
  input = sys.stdin.readline
  N = int(input())
  print(dfs(N))
  
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys

def f(n):
  X6 = []
  X9 = []
  for i in range(0, 10):
    if n >= 6**i:
      X6.append(6**i)
    if n >= 9**i:
      X9.append(9**i)
  return max(X6), max(X9)


def main():
  input = sys.stdin.readline
  N = int(input())
  dp = [0 for _ in range(N+1)]
  for i in range(1, N+1):
    can = []
    max6, max9 = f(i)
    X = [1, max6, max9]
    for x in X:
      can.append(dp[i-x] + 1)
    dp[i] = min(can)
  print(dp[N])

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys

def f(n):
  X6 = []
  X9 = []
  for i in range(1, 10):
    if n >= 6**i:
      X6.append(6**i)
    if n >= 9**i:
      X9.append(9**i)
  return X6, X9


def main():
  input = sys.stdin.readline
  N = int(input())
  dp = [0 for _ in range(N+1)]
  for i in range(1, N+1):
    can = []
    X6, X9 = f(i)
    X = [1] + X6 + X9
    for x in X:
      can.append(dp[i-x] + 1)
    dp[i] = min(can)
  print(dp[N])

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import numpy as np
import random
import queue

n = int(input())

withdraws = [1]
price = 1
while True:
    price *= 6
    if price <= 10**5 and price <= n:
        withdraws.append(price)
    else:
        break

price = 1
while True:
    price *= 9
    if price <= 10**5 and price <= n:
        withdraws.append(price)
    else:
        break


withdraws.sort()
# print(withdraws)
money = 0
count = 0


# 幅優先探索
'''
que = queue.Queue()

que.put((0,0))
memory = []
while not(que.empty()):
    money,count = que.get()
    print(money,count)
    if money > n:
        pass
    else:
        for withdraw in withdraws:
            if money+withdraw == n:
                print(count+1)
                exit()

            elif money+withdraw in memory:
                pass
            else:
                memory.append(money+withdraw)
                next = (money+withdraw,count+1)
                que.put(next)
'''
'''
# 分割

ans = 10**10
if n < 6:
    ans = n
for i in range(n+1):
    t = i
    count = 0
    while t>0:
        count += t%6
        t = t//6
    t = n - i
    while t>0:
        count += t%9
        t = t//9
    # print(ans)
    ans =min(ans,count)

print(ans)

'''

max_num = 10**5
dp = [99999999]*(n+1)
dp[0] = 0
for i in range(1,n+1):
    # print(dp)
    dp[i] = dp[i-1]+1
    k = 6
    while i>=k:
        dp[i] = min(dp[i],dp[i-k]+1)
        k *= 6
    k = 9
    while i>=k:
        dp[i] = min(dp[i],dp[i-k]+1)
        k *= 9



print(dp[n])

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import numpy as np
import random
import queue

n = int(input())

withdraws = [1]
price = 1
while True:
    price *= 6
    if price <= 10**5 and price <= n:
        withdraws.append(price)
    else:
        break

price = 1
while True:
    price *= 9
    if price <= 10**5 and price <= n:
        withdraws.append(price)
    else:
        break


withdraws.sort(reverse = True)
# print(withdraws)
money = 0
count = 0


# 幅優先探索
'''
que = queue.Queue()

que.put((0,0))
memory = []
while not(que.empty()):
    money,count = que.get()
    print(money,count)
    if money > n:
        pass
    else:
        for withdraw in withdraws:
            if money+withdraw == n:
                print(count+1)
                exit()

            elif money+withdraw in memory:
                pass
            else:
                memory.append(money+withdraw)
                next = (money+withdraw,count+1)
                que.put(next)
'''

# 分割

ans = 10**10
if n < 6:
    ans = n
for i in range(n+1):
    t = i
    count = 0
    while t>0:
        count += t%6
        t = t//6
    t = n - i
    while t>0:
        count += t%9
        t = t//9
    # print(ans)
    ans =min(ans,count)

print(ans)

Submission status: Accepted

Solution code:
s=lambda a,b:a if a<b else s(a//b,b)+a%b;n=int(input());print(min(s(i,6)+s(n-i,9)for i in range(n+1)))

Submission status: Accepted

Solution code:
N = int(input())

def f(x):
    ans = 0
    while x>0:
        ans += x%6
        x //= 6
    return ans

def g(x):
    ans = 0
    while x>0:
        ans += x%9
        x //= 9
    return ans

l = []

for x in range(N+1):
    l.append(f(x)+g(N-x))

print(min(l))

Submission status: Accepted

Solution code:
n = int(input())

def search(n,num):
    i = 1
    while True:
        if n < num**i:
            return i-1
        i += 1
        
ans = n
for i1 in range(0,6):
    for i2 in range(0,6):
        for i3 in range(0,6):
            for i4 in range(0,6):
                for i5 in range(0,6):
                    for i6 in range(0,6):
                        res = n
                        res -= (6**1)*i1+(6**2)*i2+(6**3)*i3+(6**4)*i4+(6**5)*i5+(6**6)*i6
                        if res >= 0:
                            count = i1+i2+i3+i4+i5+i6
                            while res > 6:
                                i = search(res,9)
                                cnt = int(res / (9**i))
                                res -= (9**i) * cnt
                                count += cnt
                            count += res
                            if ans > count:
                                ans = count
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

ans = 10 ** 5
for i in range(n // 9 + 1):
    m = n - 9 * i
    j, k = divmod(m, 6)
    cnt = k

    tmp = 0
    while 6 ** (tmp + 1) <= j: tmp += 1
    while tmp > 0 and j:
        jj, j = divmod(j, 6 ** tmp)
        cnt += jj
        tmp -= 1
    cnt += j

    tmp = 0
    while 9 ** (tmp + 1) <= i: tmp += 1
    while tmp > 0 and i:
        ii, i = divmod(i, 9 ** tmp)
        cnt += ii
        tmp -= 1
    cnt += i

    ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
def counting(num, power, base):
    num2 = 0
    while num >= base:
        if num >= base ** (power - 1):
            num -= base ** (power - 1)
            num2 += 1
        else:
            power -= 1
    return num + num2

def main():
    n = int(input())
    ans = float("inf")
    for n_nine in range(0, n// 9 + 1):
        s = n - 9 * n_nine
        n_six = s // 6
        n_1 = s - 6 * n_six
        pow_nine = 5
        pow_six = 6
        n_9 = counting(n_nine, pow_nine, 9)
        n_6 = counting(n_six, pow_six, 6)
        ans = min(ans, n_1 + n_6 + n_9)

    print(ans)

main()

Submission status: Accepted

Solution code:
n = int(input())
ans = float("inf")
for n_nine in range(0, n//9 + 1):
    s = n - 9 * n_nine
    n_six = s // 6
    n_one = s - 6 * n_six
    n_nine2 = 0
    n_six2 = 0
    pow_nine = 5
    pow_six = 6
    
    while n_nine >= 9:
        if n_nine >= 9 ** (pow_nine - 1):
            n_nine -= 9 ** (pow_nine - 1)
            n_nine2 += 1
        else:
          pow_nine -= 1

    while n_six >= 6:
        if n_six >= 6 ** (pow_six - 1):
            n_six -= 6 ** (pow_six - 1)
            n_six2 += 1
        else:
          pow_six -= 1          
          
    ans = min(ans, n_nine2 + n_nine + n_six2 + n_six + n_one)
          
print(ans)

Submission status: Accepted

Solution code:
def solve(n):
    dp = [100001] * (n + 1)
    dp[0] = 0
    for i in range(n):
        for j in range(10):
            if i + 6 ** j > n:
                break
            dp[i + 6 ** j] = min(dp[i + 6 ** j], dp[i] + 1)
        for j in range(10):
            if i + 9 ** j > n:
                break
            dp[i + 9 ** j] = min(dp[i + 9 ** j], dp[i] + 1)
    return dp[n]

N = int(input())
print(solve(N))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc099/tasks/abc099_c

def main():
    max_val = 10**5 + 1
    dp = [i for i in range(max_val)]

    for i in range(max_val):
        p = 1
        while p < max_val:
            dp[i] = min(dp[i], dp[i - p] + 1)
            p *= 6
        p = 1
        while p < max_val:
            dp[i] = min(dp[i], dp[i - p] + 1)
            p *= 9

    N = int(input())
    print(dp[N])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
DP=[i for i in range(100001)]
for i in range(100001):
    p=1
    while p<=i:
        DP[i]=min(DP[i],DP[i-p]+1)
        p*=6
    p=1
    while p<=i:
        DP[i]=min(DP[i],DP[i-p]+1)
        p*=9
print(DP[n])