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

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]

from collections import defaultdict, deque
from sys import exit
import heapq
import math
import copy
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)

mod = 10 ** 9 + 7

N = getN()
splitlist = [1]
splitsix = 6
while splitsix < 100000:
    splitlist.append(splitsix)
    splitsix *= 6
splitnine = 9
while splitnine < 100000:
    splitlist.append(splitnine)
    splitnine *= 9
splitlist.sort()

splitlist.reverse()

ans = float('inf')
dp = [float('inf')] * (N + 1)
dp[0] = 0


for i in range(N + 1):
    for k in splitlist:
        if i >= k:
            dp[i] = min(dp[i], dp[i - k] + 1)
print(dp[-1])

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]

from collections import defaultdict, deque
from sys import exit
import heapq
import math
import copy
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)

mod = 10 ** 9 + 7

N = getN()
splitlist = [1]
splitsix = 6
while splitsix < 100000:
    splitlist.append(splitsix)
    splitsix *= 6
splitnine = 9
while splitnine < 100000:
    splitlist.append(splitnine)
    splitnine *= 9
splitlist.sort()

splitlist.reverse()

ans = float('inf')
dp = [float('inf')] * (N + 1)
dp[0] = 0

def spliter(n):
    if dp[n] < 1000000:
        return dp[n]
    res = float('inf')
    for split in splitlist:
        if n >= split:
            res = min(res, spliter(n - split) + 1)
    dp[n] = res
    return res
spliter(N)
print(dp[-1])

Solution (Python):
n = int(input())
dp = [float('Inf')] * (n + 1)
dp[0] = 0
for i in range(1, n + 1):
    j = 1
    while j <= i:
        dp[i] = min(dp[i], dp[i - j] + 1)
        j *= 6
    j = 1
    while j <= i:
        dp[i] = min(dp[i], dp[i - j] + 1)
        j *= 9
print(dp[n])

Solution (Python):
n = int(input())
dp = [float('Inf')] * (n + 1)
dp[0] = 0
for i in range(1, n + 1):
    j = 1
    while j <= i:
        dp[i] = min(dp[i], dp[i - j] + 1)
        j *= 6
    j = 1
    while j <= i:
        dp[i] = min(dp[i], dp[i - j] + 1)
        j *= 9
print(dp[n])

Solution (Python):
def s(n, r):
  if n == 0:
    return 0
  return n % r + s(n // r, r)
n = int(input())
ans = 100000
for i in range(n + 1):
  ans = min(ans, s(i, 6) + s(n - i, 9))
print(ans)

Solution (Python):
n = int(input())
dp = [float('Inf')] * (100000 + 1)
dp[0] = 0
for i in range(1, n + 1):
    dp[i] = dp[i - 1] + 1
    cnt = 1
    for j in range(0, 7):
        cnt *= 6 
        if i - cnt >= 0:
            dp[i] = min(dp[i], dp[i - cnt] + 1)
    cnt = 1
    for j in range(0, 6):
        cnt *= 9
        if i - cnt >= 0:
            dp[i] = min(dp[i], dp[i - cnt] + 1)
print(dp[n])

Solution (Python):
def main():
    N = int(input())
    dp = [i for i in range(N + 1)]
    pow6 = 6
    while pow6 <= N:
        for i in range(N + 1):
            if i + pow6 > N:
                break
            dp[i + pow6] = min([dp[i + pow6], 1 + dp[i]])
        pow6 *= 6
    pow9 = 9
    while pow9 <= N:
        for i in range(N + 1):
            if i + pow9 > N:
                break
            dp[i + pow9] = min([dp[i + pow9], 1 + dp[i]])
        pow9 *= 9
    print(dp[N])


if __name__ == '__main__':
    main()

Solution (Python):
def checkmin(i):
    six_k = 1
    nine_k = 1
    list_before_compare = []
    list_before_compare.append(dp_table[i])
    
    
    list_before_compare.append(dp_table[i-1] + 1)
    
    
    while 6**six_k <= i:
        list_before_compare.append(dp_table[i-6**six_k] + 1)
        six_k += 1
    
    
    while 9**nine_k <= i:
        list_before_compare.append(dp_table[i-9**nine_k] + 1)
        nine_k += 1

    return min(list_before_compare)    

n = int(input())

dp_table = [float("inf")] * (n+1)


dp_table[0] = 0

for i in range(1,n+1):
    dp_table[i] = checkmin(i)

print(dp_table[-1])

Solution (Python):
n = int(input())
count=n
for i in range(0,n+1):
  temp=0
  temp6=i
  while temp6>0:
    temp=temp+temp6%6
    temp6=int(temp6/6)
  temp9=n-i
  while temp9>0:
    temp=temp+temp9%9
    temp9=int(temp9/9)
  count=min(count,temp)
print(count)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    ans=INF
    for i in range(N+1):
        tmp=0
        n=i
        while n>0:
            tmp+=n%6
            n//=6
        m=N-i
        while m>0:
            tmp+=m%9
            m//=9
        ans=min(ans,tmp)
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
mi=n
for k in range(n+1):
    six=0
    nine=0
    k2=n-k
    while k>0:
        six+=k%6
        k//=6
    while k2>0:
        nine+=k2%9
        k2//=9
    mi=min(mi,six+nine)
print(mi)

Solution (Python):
N=int(input())
L=[1]
for i in range(1,100):
    a=6**i
    if a<=100000:
        L.append(a)
    else:
        break
for i in range(1,100):
    a=9**i
    if a<=100000:
        L.append(a)
    else:
        break
dp=[1000000]*(N+1)
dp[0]=0
for i in range(1,N+1):
    sub=10**5
    for l in L:
        if i-l>=0:
            sub=min(sub, dp[i-l]+1)
    dp[i]=sub

print(dp[N])

Solution (Python):
N = int(input())

memo = [N+1] * (N+1)

memo[0] = 0
memo[1] = 1

exp_sixs = []
exp_nines = []

for i in range(1, 100000):
    if 6 ** i <= N:
        exp_sixs.append(6**i)
    else:
        break

for i in range(1, 100000):
    if 9 ** i <= N:
        exp_nines.append(9**i)
    else:
        break



for exp_six  in exp_sixs:
    memo[exp_six] = 1

for exp_nine in exp_nines:
    memo[exp_nine] = 1

for i in range(1, N+1):
    
    one_result = memo[i-1] + 1

    
    six_result = N+1
    for exp_six in exp_sixs:
        if (i - exp_six) >= 0:
            six_result = min(six_result, memo[i-exp_six] + 1)
        else:
            break

    
    nine_result = N+1
    for exp_nine in exp_nines:
        if (i - exp_nine) >= 0:
            nine_result = min(nine_result, memo[i-exp_nine] + 1)
        else:
            break
    memo[i] = min(one_result, six_result, nine_result)
print(memo[N])

Solution (Python):
N = int(input())
money = [1]
i = 1
while True:
    i *= 6
    if i <= 100000:
        money.append(i)
    else:
        break
i = 1
while True:
    i *= 9
    if i <= 100000:
        money.append(i)
    else:
        break

M = len(money)

dp = [[10 ** 9 for _ in range(N + 1)] for _ in range(M + 1)]

for i in range(M + 1):
    dp[i][0] = 0

for i in range(1, M + 1):
    for j in range(N + 1):
        if j - money[i - 1] >= 0:
            dp[i][j] = min(dp[i][j - money[i - 1]] + 1, dp[i - 1][j])
        else:
            dp[i][j] = dp[i - 1][j]

print(dp[M][N])

Solution (Python):
N = int(input())
INF = 10**18
dp = [-1] * (100000 + 1)
dp[0] = 0

V = [1]
i = 1
while 9**i < 100000:
    dp[9**i] = 1
    V.append(9**i)
    i += 1
i = 1
while 6**i < 100000:
    dp[6**i] = 1
    V.append(6**i)
    i += 1


for i in range(1, 100000 + 1):
    if dp[i] != -1:
        continue
    _min = INF
    for v in V:
        if i - v < 0:
            continue
        _min = min(_min, dp[i - v] + 1)
    dp[i] = _min

print(dp[N])

Solution (Python):
n = int(input())
dp = [float('inf')]*n
draw = [1] + [6**i for i in range(1, 7)] + [9**i for i in range(1, 6)]
for a in draw:
    if a-1 < n:
        dp[a-1] = 1
for i in range(n):
    for j in draw:
        if i+j < n:
            dp[i+j] = min(dp[i+j], dp[i]+1)
print(dp[-1])

Solution (Python):
n = int(input())
dp = [float('inf')]*n
amt = [1] + [6**i for i in range(1, 7)] + [9**i for i in range(1, 6)]
for a in amt:
    if a-1 < n:
        dp[a-1] = 1
for i in range(n):
    for j in amt:
        if i+j < n:
            dp[i+j] = min(dp[i+j], dp[i]+1)
print(dp[-1])

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())
N = I()
dp = [float('INF')]*(N+1) 
dp[0] = 0
for i in range(N+1):
    if i-1>=0:
        dp[i] = min(dp[i],dp[i-1]+1)
    num6,num9 = 6,9
    while i-num6>=0:
        dp[i] = min(dp[i],dp[i-num6]+1)
        num6 *= 6
    while i-num9>=0:
        dp[i] = min(dp[i],dp[i-num9]+1)
        num9 *= 9
print(dp[-1])

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())
N = I()
dp = [float('INF')]*(N+1) 
dp[0] = 0
for i in range(N+1):
    if i+1<=N:
        dp[i+1] = min(dp[i+1],dp[i+1],dp[i]+1)
    num6,num9 = 6,9
    while i+num6<=N:
        dp[i+num6] = min(dp[i+num6],dp[i]+1)
        num6 *= 6
    while i+num9<=N:
        dp[i+num9] = min(dp[i+num9],dp[i]+1)
        num9 *= 9
print(dp[-1])

Solution (Python):
n = int(input())
c = [1]
x = 6
while x <= n:
    c.append(x)
    x *= 6
x = 9
while x <= n:
    c.append(x)
    x *= 9
l = len(c)
dp = [[float("inf")]*(n+1) for _ in range(l+1)]
dp[0][0] = 0
for i in range(l):
    for yen in range(n+1):
        if yen - c[i] < 0: dp[i+1][yen] = dp[i][yen]
        else: dp[i+1][yen] =  min(dp[i][yen],dp[i+1][yen-c[i]]+1)

print(dp[l][n])

Solution (Python):
n = int(input())
A = [0, 1] + [6**i for i in range(1, 7)] + [9**i for i in range(1, 6)]
dp = [10**6] * (10**6 + 1)
dp[0] = 0
for i in range(1, n+1):
    dp[i] = min(dp[i-a]+1 for a in A if i>=a)
print(dp[n])

Solution (Python):
n=int(input())
ans=n
for i in range(n+1):
    cnt=0
    t=i
    while t>0:
        cnt+=t%6
        t//=6
    j=n-i
    while j>0:
        cnt+=j%9
        j//=9
    ans=min(ans,cnt)
print(ans)

Solution (Python):
n = int(input())
dp = [float("INF") for i in range(n+1)]
dp[0] = 0

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

Solution (Python):
import itertools,sys
def I(): return int(sys.stdin.readline().rstrip())
N = I()
dp = [float('INF')]*(N+1)
dp[0] = 0
for i in range(N+1):
    if i+1<=N:
        dp[i+1] = min(dp[i+1],dp[i]+1)
    num6,num9 = 6,9
    while i+num6<=N:
        dp[i+num6] = min(dp[i+num6],dp[i]+1)
        num6 *= 6
    while i+num9<=N:
        dp[i+num9] = min(dp[i+num9],dp[i]+1)
        num9 *=9
print(dp[-1])

Solution (Python):
import itertools,sys
def I(): return int(sys.stdin.readline().rstrip())
N = I()
dp = [float('INF')]*(N+1)
dp[0] = 0
for i in range(N+1):
    if i+1<=N:
        dp[i+1] = min(dp[i+1],dp[i]+1)
    num6,num9 = 6,9
    while i+num6<=N:
        dp[i+num6] = min(dp[i+num6],dp[i]+1)
        num6 *= 6
    while i+num9<=N:
        dp[i+num9] = min(dp[i+num9],dp[i]+1)
        num9 *=9
print(dp[-1])

Solution (Python):
import itertools,sys
def I(): return int(sys.stdin.readline().rstrip())
N = I()
if N<=5:
    print(N)
    exit()
dp = [float('INF')]*(N+1)
dp[0] = 0
num6,num9 = 6,9
d6d9 = set()
while num6<=N:
    d6d9.add(num6)
    num6 *= 6
while num9<=N:
    d6d9.add(num9)
    num9 *= 9
for i,x in itertools.product(range(N+1),d6d9):
    if i+x>=N+1:
        continue
    dp[i+1] = min(dp[i+1],dp[i]+1)
    dp[i+x] = min(dp[i+x],dp[i]+1)
print(dp[-1])

Solution (Python):
import itertools,sys
def I(): return int(sys.stdin.readline().rstrip())
N = I()
if N<=5:
    print(N)
    exit()
dp = [float('INF')]*(N+1)
dp[0] = 0
num6,num9 = 6,9
d6d9 = set()
while num6<=N:
    d6d9.add(num6)
    num6 *= 6
while num9<=N:
    d6d9.add(num9)
    num9 *= 9
for i,x in itertools.product(range(N+1),d6d9):
    if i+x>=N+1:
        continue
    dp[i+1] = min(dp[i+1],dp[i]+1)
    dp[i+x] = min(dp[i+x],dp[i]+1)
print(dp[-1])

Solution (Python):
N=int(input())
dp=[float('inf') for i in range(N+1)]
dp[0]=0

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

Solution (Python):
N=int(input())
dp=[float('inf') for i in range(100001)]
dp[0]=0

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

Solution (Python):
def solve():
    N = int(input())
    dp = [float('inf')] * (N+1)
    dp[0] = 0

    for i in range(1,N+1):
        
        dp[i] = min(dp[i], dp[i-1]+1)

        
        n = 1
        while i - pow(6,n) >= 0:
            dp[i] = min(dp[i], dp[i-pow(6,n)]+1)
            n += 1

        
        n = 1
        while i - pow(9,n) >= 0:
            dp[i] = min(dp[i], dp[i-pow(9,n)]+1)
            n += 1
    
    print(dp[-1])

if __name__ == '__main__':
    solve()

Solution (Python):
n = int(input())
dp = [100000000000 for _ in range(n+1)]
dp[0] = 0
for i in range(1,n+1):
    dp[i] = min(dp[i-1]+1,dp[i])
    six = 0
    nine = 0
    while (6**six <= i):
        dp[i] = min(dp[i - 6**six] + 1,dp[i])
        six += 1
    while (9**nine <= i):
        dp[i] = min(dp[i - 9**nine] + 1,dp[i])
        nine += 1
print(dp[n])

Solution (Python):
N = int(input())
INF = int(1e10)
dp = [INF] * N
dp[0] = 1
dp = [0] + dp

bt = set()
for i in range(1, 100):
    if 6**i > N:
        break
    bt.add(6**i)

for i in range(1, 100):
    if 9**i > N:
        break
    bt.add(9**i)

bt = sorted(bt)

for i in range(1, N+1):
    dp[i] = dp[i-1] + 1
    for j in bt:
        if i - j >= 0:
            dp[i] = min(dp[i], dp[i - j] + 1)

print(dp[N])

Solution (Python):
import numpy as np
n = int(input())

lim = 10 ** 18
dp = [lim] * (n + 1)
dp[0] = 0

check = [1]

temp = 6
while (temp <= n):
    check.append(temp)
    temp *= 6


temp = 9
while (temp <= n):
    check.append(temp)
    temp *= 9



for i in range(1, n + 1):
    for cc in check:
        temp = i - cc
        if (temp >= 0):
            dp[i] = min(dp[i], dp[temp] + 1)
            
            
            
            

print(dp[n])

Solution (Python):
N = int(input())
count = 0

values = [1]

for i in range(1, 7):
    values.append(6**i)
    values.append(9**i)

values.sort()


dp =  [99999999] * (N+1)
dp[0] = 0

for i in range(1, N+1):
    for j in values:
        if i - j >= 0:
            dp[i] = min(dp[i], dp[i-j]+1)

print(dp[N])

Solution (Python):
n = int(input())
ans = n
for i in range(n + 1):
    cc = 0
    t = i
    while t > 0:
        cc += t % 6
        t //= 6
    t = n - i
    while t > 0:
        cc += t % 9
        t //= 9
    ans = min(ans, cc)
print(ans)

Solution (Python):
def main():
    import bisect
    n = int(input())
    m = [10 ** 5 for _ in range(n + 1)]
    m[0] = 0
    a = [6 ** i for i in range(7)]
    b = [9 ** i for i in range(6)]
    c = sorted(a + b)
    for i in range(1, n + 1):
        j = bisect.bisect_right(c, i)
        k = [1 + m[i - x] for l, x in enumerate(c) if l < j]
        m[i] = min(k)

    print(m[-1])


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    n = int(input())
    m = [10 ** 5 for _ in range(n + 1)]
    m[0] = 0
    for i in range(1, n + 1):
        j = 0
        while i - 6 ** j >= 0:
            m[i] = min(1 + m[i - 6 ** j], m[i])
            j += 1
        j = 0
        while i - 9 ** j >= 0:
            m[i] = min(1 + m[i - 9 ** j], m[i])
            j += 1

    print(m[-1])


if __name__ == '__main__':
    main()

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
ans = n
for i in range(n+1):
    j = n - i
    preans = 0
    while i > 0:
        preans += i % 6
        i //= 6
    while j > 0:
        preans += j % 9
        j //= 9
    ans = min(ans, preans)
print(ans)

Solution (Python):
import numpy as np
from math import log
N=int(input())

L=[1]
for i in range(1,N):
    if 6**i<=N:
        L.append(6**i)
    else:
        break
for i in range(1,N):
    if 9**i<=N:
        L.append(9**i)
    else:
        break
L=np.array(L)
dp=np.ones((N+1))*100000
dp[0]=0
dp[1]=1
for i in range(2,N+1):
    dp[i]=(dp[i-L]+1).min()

print(int(dp[N]))

Solution (Python):
from math import log
N=int(input())

L=[1]
for i in range(1,N):
    if 6**i<=N:
        L.append(6**i)
    else:
        break
for i in range(1,N):
    if 9**i<=N:
        L.append(9**i)
    else:
        break

dp=[100000]*(N+1)
dp[0]=0
dp[1]=1
for i in range(2,N+1):
    sub=100000
    for l in L:
        if i-l>=0:
            sub=min(dp[i-l]+1,sub)
    dp[i]=sub

print(dp[N])

Solution (Python):
import numpy as np
N=int(input())
six=[1]
nine=[]
for i in range(1,N):
  six.append(6**i)
  nine.append(9**i)
  if 6**i>N:
    break
six=np.array(six)
nine=np.array(nine)
L=np.concatenate([six,nine])    
now=N
count=0
dp=np.ones(N+L.max()+1)*10**5
dp[1]=1
dp[0]=0

for i in range(1,N):
  dp[i+1]=(dp[i-L+1]+1).min()

  
print(int(dp[N]))

Solution (Python):
N = int(input())
dp = [float("inf") for i in range(N+1)]
for i in range(6):
  if i <= N:
    dp[i] = i

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

for i in range(N,0,-1):
  if dp[i] != 0:
    ans = dp[i] + N-i
    break
print(ans)

Solution (Python):
def make_list(a, n):
    res = [1]
    i = 1
    while pow(a, i) <= n:
        res.append(pow(a, i))
        i += 1
    return res[::-1]


def find_withdraw_times(n, w):
    res = 0
    for ww in w:
        res += n // ww
        n %= ww
    return res


def main():
    n = int(input())
    answer = float("inf")
    way_6 = make_list(6, n)
    way_9 = make_list(9, n)
    for i in range(n + 1):
        answer = min(answer, find_withdraw_times(i, way_6) + find_withdraw_times(n - i, way_9))
    print(answer)


if __name__ == '__main__':
    main()

Solution (Python):
import math
n = int(input())

num_li = []
for i in range(10):
    num_li.append(6**i)
    num_li.append(9**i)
num_li.sort(reverse=True)

dp = [10**18 for i in range(n+1)]
dp[0]=0
for i in range(1,n+1):
    for j in num_li:
        if i-j>=0:
            dp[i]=min(dp[i],dp[i-j]+1)

print(dp[n])

Solution (Python):
N = int(input())
from math import log

max6 = int(log(N, 6))
max9 = int(log(N, 9))
dp = [10**18]*(N+1)
dp[0] = 0
for i in range(1, N+1):
    dp[i] = dp[i-1]+1
    for j in range(max6+2):
        if 6**j>i:
            break
        dp[i] = min(dp[i-6**j]+1, dp[i])
    for k in range(max9+2):
        if 9**k>i:
            break
        dp[i] = min(dp[i-9**k]+1, dp[i])

print(dp[-1])

Solution (Python):
n=int(input())
m=[int(pow(6,i)) for i in range(7)]
m9=[int(pow(9,i)) for i in range(1,6)]
m+=m9
m.sort(reverse=True)

dp=[10**18 for i in range(n+1)]
dp[0]=0
for i in range(1,n+1):
  for j in m:
    if i-j>=0:
      dp[i]=min(dp[i],dp[i-j]+1)

print(dp[n])

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    List = [1]

    for i in range(1, 7):
        List.append(pow(6, i))
        List.append(pow(9, i))

    List.sort()
    dp = [f_inf for _ in range(n + 1)]
    dp[0] = 0

    for i in range(1, n + 1):
        for L in List:
            if i - L >= 0:
                dp[i] = min(dp[i], dp[i - L] + 1)

    print(dp[n])


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys
import re
import math
import collections

import bisect







INF = sys.maxsize


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))





def main():
    n = ni()
    l = 10 ** 5 + 1

    items = [1]
    for i in range(10 ** 3):
        tmp6 = 6 ** i
        if tmp6 < l:
            items.append(tmp6)

        tmp9 = 9 ** i
        if tmp9 < l:
            items.append(tmp9)

    s = {0}
    for i in range(l):
        next_s = set()
        for ts in s:
            for d in items:
                if ts+d <= n:
                    next_s.add(ts+d)
        if n in next_s:
            print(i+1)
            break
        s = next_s


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())

import math

ans = float('inf')
def calc(x,cnt):
    if x<6:
        global ans
        ans = min(ans,x+cnt)
    else:
        c = 6**int(math.log(x,6))
        if c*6==x:c*=6
        calc(x-c,cnt+1)
        c = 9**int(math.log(x,9))
        if c*9==x:c*=9
        calc(x-c,cnt+1)

calc(n,0)

print(ans)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
res = [INF] * (n+1)
res[0] = 0
ge = [1]
for i in [6,9]:
    now = 1
    while True:
        now *= i
        if now > n:
            break
        ge.append(now)
ge.sort()
for i in range(1,n+1):
    for x in ge:
        if x > i:
            continue
        res[i] = min(res[i], res[i-x]+1)
print(res[n])

Solution (Python):
n = int(input())
dp = [10 ** 5 for _ in range(n + 1)]

dp[0] = 0
for i in range(1, n + 1):
    for num in [6, 9]:
        power = 1
        while power <= i:
            dp[i] = min(dp[i], dp[i - power] + 1)
            power *= num

print(dp[n])

Solution (Python):
n = int(input())

INF = 10**10
dp = [INF] * (n + 1)
dp[0] = 0
dp[1] = 1

num_list = [1]

for i in range(1, 9):
    n1 = 6**i
    n2 = 9**i
    if n1 <= n:
        num_list.append(n1)
    if n2 <= n:
        num_list.append(n2)

for i in range(0, n):
    for j in num_list:
        if i + j <= n:
            dp[i+j] = min(dp[i+j], dp[i] + 1)

print(dp[n])

Solution (Python):
from itertools import product
def count9(cur):
    count = 0
    for i in range(6)[::-1]:
        count += cur//(9**i)
        cur %= 9**i
    return count
n = int(input())
ans = count9(n)
for x in product("012345",repeat = 6):
    digitsum = 0
    SUM = 0
    for i in range(6):
        SUM += int(x[i])*6**(i+1)
        digitsum += int(x[i])
    if SUM <= n:
        ans = min(ans,digitsum+count9(n-SUM))
print(ans)

Solution (Python):
memo = {}
def f(x):
    if 0<=x<=5:
        return x
    if x in memo:
        return memo[x]
    k = 0
    while 9**k<=x:
        k += 1
    m = 0
    while 6**m<=x:
        m += 1
    memo[x] = min(f(x-9**(k-1))+1,f(x-6**(m-1))+1)
    return memo[x]
print(f(int(input())))

Solution (Python):
n=int(input())
c=[1]
i=1
while (6**i<=100000):
  c.append(6**i)
  i+=1
i=1
while (9**i<100000):
  c.append(9**i)
  i+=1
c.sort()
m=[0]
for i in range(1,n+1):
  mi=1000000
  for j in range(len(c)):
    if i-c[j]<0:
      break
    if m[i-c[j]]+1<mi:
      mi=m[i-c[j]]+1
  m.append(mi)
print(m[n])

Solution (Python):
def main():
    inf = 1 << 30

    N = int(input())

    dp = [inf] * (N + 1)
    dp[0] = 0

    for i in range(1, N + 1):
        t = inf
        x = 1
        while x <= i:
            t = min(t, dp[i - x])
            x *= 6
        x = 1
        while x <= i:
            t = min(t, dp[i - x])
            x *= 9
        dp[i] = t + 1

    print(dp[N])


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())

array = []
cnt6 = 0
while 6**cnt6 <= N:
    array.append(6**cnt6)
    cnt6 += 1
    
cnt9 = 0
while 9**cnt9 <= N:
    array.append(9**cnt9)
    cnt9 += 1

a = sorted(list(set(array)))

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

n = 6
for n in a:
    for i in range(N+1):
        if i+n <= N:
            dp[i+n] = min(dp[i]+1, dp[i+n])
print(dp[N])

Solution (Python):
n = int(input())

dp = [float('inf')]*(n+1)
dp[0] = 0
from math import log
for i in range(1,n+1):
    for j in range(int(log(n,6)+0.00001)+1):
        dp[i] = min(dp[i],dp[i-6**j]+1)
    for j in range(int(log(n,9)+0.00001)+1):
        dp[i] = min(dp[i],dp[i-9**j]+1)
print(dp[n])

Solution (Python):
N = int(input())

def digit(x, base):
    if x == 0:
        return 0
    return digit(x // base, base) + x % base

def calc(six, nine):
    return digit(six, 6) + digit(nine, 9)

ans = 10**18
for six in range(N + 1):
    ans = min(ans, calc(six, N - six))
print(ans)

Solution (Python):
n = int(input())
n0 = n
money = [1]
pow6 = 6
while pow6 <= n:
    money.append(pow6)
    pow6 *= 6




money.sort(reverse = True)

def cnt(x):
    res = 0
    while x > 0:
        res += x%9
        x = x // 9
    return res
anst = 1e100
for i in range(n0//9+1):
    ans = cnt(i)
    n = n0 - i*9
    for m in money:
        if m <= n:
            ans += n//m
            n %= m
    anst = min(anst,ans)
print(anst)

Solution (Python):
import numpy as np
N = int(input())
C = [6 ** x for x in range(8) if 6 ** x <= N]
C += [9 ** x for x in range(8) if 9 ** x <= N]

dp = np.zeros(N + 1, np.int64)
dp += 10 ** 10

for c in C:
    dp[c] = 1
for c in C:
    for _ in range(9):
        dp[c:] = np.minimum(dp[c:], dp[:-c] + 1)
print(dp[N])

Solution (Python):
n = int(input())

info = []
for i in range(20):
    v, w = 1, 1 ** i
    info.append((v, w))
    v, w = 1, 6 ** i
    info.append((v, w))
    v, w = 1, 9 ** i
    info.append((v, w))

m = len(info)
INF = 10 ** 8
dp = [[INF] * (n + 1) for i in range(m + 1)]
dp[0][0] = 0

for i in range(m):
    v, w = info[i]
    for j in range(n + 1):
        dp[i + 1][j] = min(dp[i][j], dp[i + 1][j])
        if j - w >= 0:
            dp[i + 1][j] = min(dp[i + 1][j - w] + v, dp[i + 1][j])

print(dp[-1][-1])

Solution (Python):
N = int(input())

INF = 10 ** 9

dp = [INF] * (N + 1)
dp[0] = 0

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


print (dp[N])

Solution (Python):
N = int(input())
li = [1]

six = 1
while six <= N:
    six = six*6
    li.append(six)

nine = 1
while nine <= N:
    nine = nine*9
    li.append(nine)

INF = 10**10

dp = [INF for i in range(N+1)]
dp[0] = 0

for i in range(N):
    for num in li:
        if i+num <= N:
            dp[i+num] = min(dp[i+num], dp[i] + 1)
print(dp[N])

Solution (Python):
N = int(input())

s = set()
a = 1
while a <= 100000:
    s.add(a)
    a *= 6
a = 1
while a <= 100000:
    s.add(a)
    a *= 9
s = sorted(s)

INF = float('inf')
dp = [INF] * (N+1)
dp[0] = 0
for i in range(N):
    for a in s:
        if i+a > N: break
        dp[i+a] = min(dp[i+a], dp[i] + 1)
print(dp[N])

Solution (Python):
N = int(input())

ans = 10**10
for i in range(N+1):
    cc = 0

    t = i
    while t > 0:
        cc += t % 6
        t //= 6

    t = N-i
    while t > 0:
        cc += t % 9
        t //= 9

    if ans > cc:
        ans = cc
print(ans)

Solution (Python):
def abc099_c():
    ''' maspyさんお手本 '''
    import numpy as np
    N = int(input())

    coin = [6**n for n in range(10) if 6**n <= N]  
    coin += [9**n for n in range(10) if 9**n <= N]  

    dp = np.zeros(N+1, dtype=int)
    dp += 10**9
    dp[0] = 0

    for c in coin:
        
        
        for _ in range(9):
            dp[c:] = np.minimum(dp[:-c]+1, dp[c:])

    ans = dp[N]
    print(ans)

abc099_c()

Solution (Python):
def abc099_c():
    ''' 解説PDF通り '''
    n = int(input())
    ans = n  

    
    for i in range(n+1):
        cc = 0
        t = i  
        while t > 0:
            cc += t % 6  
            t //= 6
        t = n - i  
        while t > 0:
            cc += t % 9
            t //= 9
        ans = min(cc, ans)

    print(ans)

abc099_c()

Solution (Python):
N = int(input())

lst = [1]
lst += [ 6**i for i in range(1, 10) if 6**i <= 100000]
lst += [ 9**i for i in range(1, 10) if 9**i <= 100000]
lst.sort()

dp = list(range(N+1))

for i in range(1, N+1):
    temp = []
    for j in lst:
        if j <= i:
            temp.append(dp[i-j] + 1) 
    dp[i] = min(temp)
print(dp[N])

Solution (Python):
n = int(input())

res = 100000
for i6 in range(0, n+1, 6):
    c6, c9 = 0, 0
    i9 = n - i6
    while (i6 > 0):
        c6 = c6 + (i6%6)
        i6 = i6 // 6
    while (i9 > 0):
        c9 = c9 + (i9%9)
        i9 = i9 // 9

    if c6 + c9 < res:
        res = c6 + c9

print(res)

Solution (Python):
n=int(input())
dp=[float("inf")]*(n+1)
dp[0]=0
for i in range(n):
    for j in range(1,7):
        j=6**j
        if i+j<n+1:
            dp[i+j]=min(dp[i+j],dp[i]+1)
    for j in range(1,6):
        j=9**j
        if i+j<n+1:
            dp[i+j]=min(dp[i+j],dp[i]+1)
    dp[i+1]=min(dp[i+1],dp[i]+1)
print(dp[-1])

Solution (Python):
def dfs(a,b,c):
  todo=[[]]
  ret=[]
  while len(todo)>0:
    t=todo.pop()
    l=len(t)
    if l==a:
      ret.append(t)
    else:
      s=0
      for i in range(1,l+1):
        s+=6**i*t[i-1]
      for i in range(b+1):
        if s+6**(l+1)*i<=c:
          tc=t.copy()
          tc.append(i)
          todo.append(tc)
  return ret
a=6
b=5
c=int(input())
l=dfs(a,b,c)
ans=c
for li in l:
  ansi=sum(li)
  now=c-sum([6**(i+1)*li[i]for i in range(len(li))])
  for i in range(1,7):
    ansi+=now%9
    now//=9
  ans=min(ans,ansi)
print(ans)

Solution (Python):
N = int(input())
INF = float('inf')
dp = [INF]* 100001
dp[0] = 0
cost = list()
cost.append(1)
i6 = 6
while(i6 <= 100000):
  cost.append(i6)
  i6 *= 6
i9 = 9
while(i9 <= 100000):
  cost.append(i9)
  i9 *= 9
cost.sort()
for i in range(1, 100001):
  for c in cost:
    if(i-c>=0):
      dp[i] = min(dp[i], dp[i-c]+1)
print(dp[N])

Solution (Python):
n = int(input())

dp = [float('inf')]*(10**5+1)
dp[0] = 0
import math

for i in range(1,10**5+1):
    for j in range(int(math.log(i,9)+0.00001)+1):
        dp[i] = min(dp[i], dp[i-9**j]+1)

    for k in range(int(math.log(i,6))+1):
        dp[i] = min(dp[i],dp[i-6**k]+1)
 
print(dp[n])

Solution (Python):
n = int(input())

dp = [n] * 110000
dp[0] = 0

for i in range(n):
    j = 0
    while i + 6 ** j <= n:
        dp[i+6**j] = min(dp[i+6**j], dp[i]+1)
        j += 1
    k = 0
    while i + 9 ** k <= n:
        dp[i+9**k] = min(dp[i+9**k], dp[i]+1)
        k += 1

print(dp[n])