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):
n = int(input())

def sum(money,p):
	count = 0
	while money:
		count += money%p
		money = money // p
	return count

ans = 10**6
for i in range(n+1):
	ans = min(ans,sum(i,6)+sum(n-i,9))

print(ans)

Solution (Python):



n = int(input())
ls = [1]
t = 6
while t < 100000:
    ls.append(t)
    t *= 6
t = 9
while t < 100000:
    ls.append(t)
    t *= 9

ls.sort()

"""
cnt = 0
while n >= 6:
    print(n,ls)
    ls = [i for i in ls if i <= n]
    n -= ls[len(ls)-1]
    cnt += 1
print(cnt+n)
"""

dp = [10**9 for i in range(n+1)]
dp[0] = 0

for i in range(1,n+1):
    ls1 = [j for j in ls if j <= i]
    
    for j in range(len(ls1)):
        
        dp[i] = min(dp[i],dp[i - ls1[j]] + 1)

print(dp[n])

Solution (Python):
n = int(input())
dp = [10**9]*30000000
dp[0] = 0
pow6 = [6**i for i in range(10) if 6**i <= n]
pow9 = [9**i for i in range(10) if 9**i <= n]

for i in range(n):
    for p6 in pow6:
        dp[i+p6] = min(dp[i+p6], dp[i]+1)
    for p9 in pow9:
        dp[i+p9] = min(dp[i+p9], dp[i]+1)
print(dp[n])

Solution (Python):
def sum_digits(n, m):
    r = 0
    while n:
        r = r + n % m
        n = n // m
    return r

N = int(input())

ans = 100000
for i in range(N + 1):
    ans = min(ans, sum_digits(i, 6)+sum_digits(N - i, 9))

print(ans)

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

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

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

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

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

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

def base10to(n, b):
    if (int(n/b)):
        return base10to(int(n/b), b) + str(n%b)
    return str(n%b)

mod9 = N//9
res = 10**10

for i in range(0,mod9+1):
    j = (N-i*9)//6
    cnt = 0
    if 9*i+6*j > N:
        break
    else:
        t = base10to(i,9)
        s = base10to(j,6)
        for x in str(t):
            cnt += int(x)
        for y in str(s):
            cnt += int(y)
        cnt += (N-9*i-6*j)
        if cnt <= res:
            res = cnt
print(res)

Solution (Python):
N = int(input())
ans = N
for i in range(N+1):
  t = i
  cc = 0
  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):
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

    if ans > cc:
        ans = cc

print(ans)

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

    if ans > cc:
        ans = cc

print(ans)

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

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

print(dp[N])

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

Solution (Python):
import math
N = int(input())
dp = [10**15] * 1000000
dp[1] = 1
dp[0] = 0
for i in range(N + 1):
    dp[i + 1] = min (dp[i] + 1 , dp[i + 1])
    for k in range(7):
        dp[i + 6 ** k ] = min (dp[i] + 1 ,dp[i + 6 ** k ])
    for k in range( 7):
        dp[i + 9 ** k] = min(dp[i] + 1, dp[i + 9 ** k])
print(dp[N])

Solution (Python):
from functools import reduce
import math
import bisect

def main():
    
    
    
    

    
    
    
    
    
    

    
    

    
    
    
    
    
    
    
    
    
    INF = float("inf")

    
    MOD = 10**9+7
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    
    
    
    N = int(input())
    N_max = 100000
    l = []
    l.append(1)
    tmp = 1
    while tmp < N_max:
        tmp *= 6
        l.append(tmp)
    tmp = 1
    while tmp < N_max:
        tmp *= 9
        l.append(tmp)
    l.sort()
    d = [N_max for _ in range(N+1)]
    d[0] = 0
    for i in range(1,N+1):
        d[i] = d[i-1] + 1
        for j in range(len(l)):
            if i >= l[j]:
                d[i] = min(d[i],d[i-l[j]]+1)
    print(d[N])
    
if __name__ == '__main__':
    main()

Solution (Python):
import collections

N = int(input())

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




memo = set([N])
q = collections.deque([(N, 0)])
while len(q) > 0:
    n, depth = q.popleft()
    if n == 0:
        print(depth)
        break
    for w in withdraw:
        if n >= w and n-w not in memo:
            q.append((n-w, depth+1))
            memo.add(n-w)

Solution (Python):
N=int(input())
dp=[10**7]*3000000
dp[0]=0

pow6=[6**j for j in range(10) if 6**j <= N]
pow9=[9**j for j in range(10) if 9**j <= N]

for i in range(N):
    for p6 in pow6:
        dp[i+p6]=min(dp[i+p6], dp[i]+1)
    for p9 in pow9:
        dp[i+p9]=min(dp[i+p9], dp[i]+1)

print(dp[N])

Solution (Python):







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

Solution (Python):

coin_list = sorted([1] + [ 6**i for i in range(1,7) ] + [ 9**i for i in range(1,6) ])

num_list = [ i for i in range(10**5+1) ]

for i in range(1,10**5+1):
    candidate = [ num_list[i-j] for j in coin_list if j <= i ]
    num_list[i] = min(candidate) + 1

n = int(input())
print(num_list[n])

Solution (Python):
def smaller(x, y):
	if x < y: return x
	return y

lst = [1]
x = 6
while x <= 100000:
	lst.append(x)
	x *= 6
x = 9
while x <= 100000:
	lst.append(x)
	x *= 9
lst.sort()

N = int(input())
dp = []
for i in range(0, N+1):
	dp.append(100001)
dp[0] = 0
for i in range(0, N):
	for j in range(0, len(lst)):
		if i + lst[j] > N:
			break
		dp[i+lst[j]] = smaller(dp[i+lst[j]], dp[i]+1)
print(dp[N])

Solution (Python):
N = int(input())
xs = [1]
i = 1
while N >= 6**i:
    if 9**i <= N:
        xs.append(9**i)
    xs.append(6**i)
    i += 1
X = sorted(xs)



dp = [10000000000] * 1008000
dp[0] = 0
for i in range(N):
    for x in X:
        dp[i+x] = min(dp[i]+1, dp[i+x])
print(dp[N])

Solution (Python):
def resolve():
    n = int(input())
    a = [1]
    x = 6
    while x<=n:
        a.append(x)
        x=x*6
    x = 9
    while x<=n:
        a.append(x)
        x=x*9
    a = list(set(a))
    a.sort()
    dp = [10**9]*(n+5)
    dp[0]=0
    for i in range(1,n+1):
        for j in a:    
            if(i>=j):
                dp[i]=min(dp[i],dp[i-j]+1)
            else:
                break
    print(dp[n])


if __name__ == "__main__":
    resolve()

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

Solution (Python):
import sys

def input():
    return sys.stdin.readline().rstrip()

if __name__ == "__main__":
    n = int(input())
    l = [1] + [6**i for i in range(1, 8) if 6**i <= n] + [9**i for i in range(1, 7) if 9**i <= n]
    l.sort()

    inf = float("inf")
    dp = [inf for i in range(n+1)]
    dp[0] = 0

    for i in range(n):
        for e in l:
            if i + e <= n:
                dp[i+e] = min(dp[i] + 1, dp[i+e])
            else:
                break

    print(dp[n])

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

ans = n
for i in range(n+1):
    tmp_ans = 0
    m = i
    while m > 0:
        tmp_ans += m % 6
        m = m // 6
    m = n - i
    while m > 0:
        tmp_ans += m % 9
        m = m // 9

    ans = min(ans, tmp_ans)

print(ans)

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

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

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

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

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

Solution (Python):
N = int(input())
ops =[6**i for i in range(7)] + [9 ** i for i in range(1,6)]
ops.sort()
dp = [10*5+5]*(N+1)
dp[0]=0
for i in range(1,N+1):
    for s in range(len(ops)):
        if i-ops[s]>=0:
            dp[i] = min(dp[i-ops[s]]+1,dp[i])
print(dp[N])

Solution (Python):
def Joulist(n, m):
    ans = []
    i = m // 3
    while i <= n:
        ans.append(i)
        i *= m
    return ans


n = int(input())
dp = [1000000] * (n//3 + 1)
dp[0] = 0
for i in range(2, n//3+1):
    kouho = Joulist(i, 6) + Joulist(i, 9)
    dp[i] = min([dp[i-k] for k in kouho]) + 1
if n != 3:
    print(dp[n//3] + n%3)
else:
    print(3)

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



dp = [x for x in range(1000010)]


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


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


ans = dp[n]
print(ans)

Solution (Python):
from sys import stdin














N = int(stdin.readline().rstrip())
dp = [k for k in range(N + 1)]

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

print(dp[N])

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



dp = [x for x in range(1000010)]


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


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


ans = dp[n]
print(ans)

Solution (Python):

n = int(input())

dp = [float("INF")] * 1000010
dp[0] = 0


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


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


ans = dp[n]
print(ans)

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

dp = [float("INF")] * 1000010
dp[0] = 0


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


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


ans = dp[n]
print(ans)

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

m=[1,6,6**2,6**3,6**4,6**5,6**6,9,9**2,9**3,9**4,9**5]
m.sort()
cnt=[0]*(N+1)
for i in range(1,N+1):
    
    formararr=[]
    for l in m:
        
        if i>=l:
            formararr.append(cnt[i-l])
        cnt[i]=min(formararr)+1
print(cnt[N])

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

l6 = [6**i for i in range(1,7)]
l9 = [9**i for i in range(1,6)]

l = [1]+l6+l9

dp=[10**8 for _ in range(n+1)]

for i in range(1,n+1):
    for j in l:
        if i == j:
            dp[i]= 1
        elif i>j:
            if dp[i-1]!=0:
                dp[i] = min(dp[i],dp[i-j]+1)
            else:
                pass

print(dp[n])

Solution (Python):

import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np
import statistics
from statistics import mean, median,variance,stdev
import math

def main():
	N = int(input())
	
	DP = [i for i in range(100010)]
	
	for i in range(1, 100001):
		for j in range(1, i):
			step = 6**j
			if step > i:
				break
			tmp = 1 + DP[i-step]
			DP[i] = min(DP[i], tmp)
			
	for i in range(1, 100001):
		for j in range(1, i):
			step = 9**j
			if step > i:
				break
			tmp = 1 + DP[i-step]
			DP[i] = min(DP[i], tmp)
	
	print(DP[N])
			
	
if __name__ == "__main__":
	main()

Solution (Python):
N = int(input())
 
DP = list(range(N+1))
L = []

i = 1
while True:
    if 6**i > N:
        break
    L.append(6**i)
    i += 1
 
i = 1
while True:
    if 9**i > N:
        break
    L.append(9**i)
    i += 1

for l in sorted(L):
    for j in range(l, N+1):
        DP[j] = min(DP[j], DP[j-l] + 1)

print(DP[-1])

Solution (Python):
def Joulist(N,m):
    ans = []
    i = m//3
    while i<=N:
        ans.append(i)
        i *= m
    return ans
    

N=int(input())
DP = [1000000] * (N//3 + 1)
DP[0] = 0
for i in range(2,N//3 + 1):
    kouho = Joulist(i,6)+Joulist(i,9)
    DP[i] = min([DP[i-k] for k in kouho]) + 1
if N!=3:print(DP[N//3] + N%3)
else:print(3)

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

dp = [10**6] * (N+1)
dp[0] = 0

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

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

Solution (Python):

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


if __name__ == "__main__":
    main()

Solution (Python):
def powerset(n, lessequal):
    retval = []
    power = n
    while power <= lessequal:
        retval += [power]
        power *= n
    return retval


def main():
    N = int(input())
    dp = [0] * (N + 1)
    for i in range(1, N + 1):
        withdraw = [1] + powerset(6, i) + powerset(9, i)
        dp[i] = min([dp[i - x] for x in withdraw]) + 1
    print(dp[N])


if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
num = [1, 6, 6**2, 6**3, 6**4, 6**5, 6**6, 9, 9**2, 9**3, 9**4, 9**5]
answer = [0]*(n+1)
for i in range(1, n+1):
    answer[i] = min([answer[i-l]+1 for l in num if i-l>=0])
print(answer[n])

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

Solution (Python):
table = [0]+[1]+[10**10 for i in range(10**6)]
six = [6 ** i for i in range(1,8)]
nine = [9 ** i for i in range(1,7)]
for i in range(10**5):
    table[i+1] = min(table[i+1],table[i]+1)
    for x in six:
        table[i + x] = min(table[i + x], table[i]+1 )
    for y in nine:
        table[i+y] = min(table[i+y], table[i]+1)
print(table[int(input())])

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

dp = [10**10] * (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
        
for i in range(1,n+1):
    power = 1
    while power <= i:
        dp[i] = min(dp[i], dp[i-power] + 1)
        power *= 9
        
print(dp[-1])

Solution (Python):
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N = n()

min_count = N
for i in range(N+1):
    count = 0
    t = i
    while t > 0:
        count += t % 6
        t //= 6

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

    if count < min_count:
        min_count = count
print(min_count)

Solution (Python):
N=int(input())
list1=[0]*(N+1)
for i in range(1,N+1):
	list2=[list1[i-1]]
	l=list2.append
	if i>=6:
		l(list1[i-6])
		if i>=9:
			l(list1[i-9])
			if i>=36:
				l(list1[i-36])
				if i>=81:
					l(list1[i-81])
					if i>=216:
						l(list1[i-216])
						if i>=729:
							l(list1[i-729])
							if i>=1296:
								l(list1[i-1296])
								if i>=6561:
									l(list1[i-6561])
									if i>=7776:
										l(list1[i-7776])
										if i>=46656:
											l(list1[i-46656])
											if i>=59049:
												l(list1[i-59049])
	list1[i]=min(list2)+1
print(list1[N])

Solution (Python):
N = int(input())
dp = [-1] * (N + 1)
dp[0] = 0
l = [1] + [6**i for i in range(1,7)] + [9**i for i in range(1,6)]

for n in range(1, N+1):
    tmp = float('inf')
    for j in l:
        if n-j >= 0:
            tmp = min(tmp, 1 + dp[n-j])
    dp[n] = tmp
print(dp[-1])

Solution (Python):

N = int(input())

lis = [0]

for i in range(N):

    i += 1

    now = lis[ i - 1 ] + 1

    cnt = 1
    while True:

        if i - ( 6 ** cnt )  >= 0:
            now = min(now, lis[i - ( 6 ** cnt )] + 1)
            cnt += 1

        else:
            break

    cnt = 1
    while True:

        if i - ( 9 ** cnt )  >= 0:
            now = min(now, lis[i - ( 9 ** cnt )] + 1)
            cnt += 1

        else:
            break

    
    lis.append(now)

print (lis[N])

Solution (Python):
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=np.int32)
dp += 10**9
dp[0] = 0

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

answer = dp[-1]
print(answer)

Solution (Python):
N = int(input())
INF = 10**18

dp = [INF]*(N+1)
dp[0] = 0
for i in range(N+1):
    n6 = 6
    n9 = 9
    if i+1 < N+1:
        dp[i+1] = min(dp[i+1],dp[i]+1)
    while n6 < N+1:
        if i+n6 < N+1:
            dp[i+n6] = min(dp[i+n6],dp[i]+1)
        n6 *= 6
    while n9 < N+1:
        if i+n9 < N+1:
            dp[i+n9] = min(dp[i+n9],dp[i]+1)
        n9 *= 9

print(dp[N])

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

A = []
for i in range(1, N+1):
    if 6**i > N:
        break
    else:
        A.append(6**i)
    if 9**i <= N:
        A.append(9**i)
A.sort(reverse=True)

money = [i for i in range(N+1)]
for i in A:
    for j in range(i,N+1):
        money[j] = min(money[j], money[j-i]+1)
print(money[N])

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

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

Solution (Python):
def f(N,x):
    ret=0
    while N>=x:
        ret+=N%x
        N=N//x
    return(ret+N)

N=int(input())
ans=[]
for i in range(N+1):
    ans.append(f(i,6)+f(N-i,9))
print(min(ans))

Solution (Python):

N = int(input())
dp=[float('inf')]*110000
dp[0] = 0
for n in range(1,N+1):
    pow6 = 1
    pow9 = 1
    while pow6 <= n:
        dp[n] = min(dp[n],dp[n-pow6]+1)
        pow6 *= 6
    while pow9 <= n:
        dp[n] = min(dp[n],dp[n-pow9]+1)
        pow9 *= 9
print(dp[N])

Solution (Python):
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)
"""

memo = [-1]*(110000)
def rec(n):
    if n==0:
        return 0
    if memo[n] != -1:
        return memo[n]
    res = n
    pow6,pow9 = 1,1
    while pow6 <=n:
        res = min(res,rec(n-pow6)+1)
        pow6 *= 6
    while pow9 <= n:
        res = min(res,rec(n-pow9)+1)
        pow9 *= 9
    memo[n] = res
    return memo[n]
N = int(input())
print(rec(N))
"""
"""

N = int(input())
dp=[inf]*110000
dp[0] = 0
for n in range(1,N+1):
    pow6,pow9 = 1,1
    while pow6<=n:
        dp[n] = min(dp[n],dp[n-pow6]+1)
        pow6 *= 6
    while pow9 <= n:
        dp[n] = min(dp[n],dp[n-pow9]+1)
        pow9 *= 9
print(dp[N])
"""

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

Solution (Python):
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

N = int(input())
dp=[inf]*110000
dp[0] = 0
for n in range(1,N+1):
    pow6,pow9 = 1,1
    while pow6<=n:
        dp[n] = min(dp[n],dp[n-pow6]+1)
        pow6 *= 6
    while pow9 <= n:
        dp[n] = min(dp[n],dp[n-pow9]+1)
        pow9 *= 9
print(dp[N])

Solution (Python):
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

memo = [-1]*(110000)
def rec(n):
    if n==0:
        return 0
    if memo[n] != -1:
        return memo[n]
    res = n
    pow6,pow9 = 1,1
    while pow6 <=n:
        res = min(res,rec(n-pow6)+1)
        pow6 *= 6
    while pow9 <= n:
        res = min(res,rec(n-pow9)+1)
        pow9 *= 9
    memo[n] = res
    return memo[n]

N = int(input())
print(rec(N))

Solution (Python):


N = int(input())
dp = [110000]*(N+1)
dp[0] = 0
for i in range(1, N + 1):
    dp[i] = dp[i-1]+1
    p6 = 1
    p9 = 1
    while i >= 6 ** p6:
        dp[i] = min(1 + dp[i - 6 ** p6],dp[i])
        p6 += 1
    while i >= 9 ** p9:
        dp[i] = min(1 + dp[i - 9 ** p9],dp[i])
        p9 += 1


print(dp[N])

Solution (Python):


N = int(input())
dp = [0]
for i in range(1, N + 1):
    Q = []
    Q.append(1 + dp[i - 1])
    
    p6 = 1
    p9 = 1
    while i >= 6 ** p6:
        Q.append(1 + dp[i - 6 ** p6])
        p6 += 1
    while i >= 9 ** p9:
        Q.append(1 + dp[i - 9 ** p9])
        p9 += 1
    dp.append(min(Q))


print(dp[N])

Solution (Python):
n = int(input())
c = [1]
for i in range(6):
    c.append(6**(i+1))
for i in range(5):
    c.append(9**(i+1))
INF = float("inf")
 
dp = [INF]*(n+1)
dp[0] = 0
 
for i in range(len(c)):
    for j in range(n+1):
        if j - c[i] < 0:
            continue
        else:
            dp[j] = min(dp[j], dp[j - c[i]] + 1)
 
print(dp[n])

Solution (Python):
n = int(input())
c = [1]
for i in range(6):
    c.append(6**(i+1))
for i in range(5):
    c.append(9**(i+1))
INF = float("inf")

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

for i in range(len(c)):
    for j in range(n+1):
        if j + c[i] > n:
            break
        else:
            dp[j + c[i]] = min(dp[j + c[i]], dp[j] + 1)

print(dp[n])

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def I(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():
  l=[inf]*100001
  l[0]=0

  l2=[1]
  for i in range(1,10):
    a=pow(6,i)
    b=pow(9,i)
    if a<=100000:
      l2.append(a)
    if b<=100000:
      l2.append(b)
  l2.sort()

  n=I()

  for i in range(1,n+1):
    for x in l2:
      if i-x>=0:
        l[i]=min(l[i],l[i-x]+1)

  return l[n]

print(main())

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

dp[0] = 0
dp[1] = 1

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

Solution (Python):
import sys

from collections import deque  
from collections import defaultdict  
from heapq import heapify, heappush, heappop, heappushpop  
from bisect import bisect_left, bisect_right  




s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    total = 1e+6
    for i in range(N+1):
        a = i
        b = N - i
        c = 0
        while a > 0:
            d = a % 6
            c += d
            a = int(a / 6)
        while b > 0:
            d = b % 9
            c += d
            b = int(b / 9)
        if total > c:
            total = c
    print(total)

main()

Solution (Python):
n=int(input())
from copy import*
ans=[]
for i in range(n+1): 
    count=0
    money6=i
    money9=n-i
    while money6:
        count+=money6%6
        money6//=6
    while money9:
        count+=money9%9
        money9//=9
    ans.append(count)
print(min(ans))

Solution (Python):
import sys

from collections import deque

from collections import defaultdict

import heapq

import bisect





s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))


def main():
    N = i2n()
    coins = [1]
    d = 6
    while d <= N:
        coins.append(d)
        d *= 6
    d = 9
    while d <= N:
        coins.append(d)
        d *= 9
    
    
    
    
    items = [(c, 1) for c in coins]
    itemlen = len(items)
    dp = [[int(1e+6)] * (N+1) for _ in range(itemlen+1)]
    for i in range(itemlen+1):
        dp[i][0] = 0
    
    for item_id, (coin, coin_n) in enumerate(items):
        for n in range(1, N+1):
            if n - coin >= 0:
                dp[item_id+1][n] = min(dp[item_id][n], dp[item_id+1][n-coin] + coin_n)
            else:
                dp[item_id+1][n] = dp[item_id][n]
    
    print(dp[itemlen][N])


main()

Solution (Python):
n = int(input())
dp = [1e9 for i in range(100001)]
dp[0] = 0
ans = n
yen = set()
for i in range(7):
  yen.add(6**i)
  dp[6**i] = 1
for i in range(6):
  yen.add(9**i)
  dp[9**i] = 1
for i in range(1, n+1):
  for e in yen:
    if i+e<=100000:
      dp[i+e] = min(dp[i+e], dp[i]+1)
print(dp[n])

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

dp = [200000] * 200000
dp[0] = 0

for i in range(N+1):
    for j in range(i+1):
        tmp = 6**j
        if tmp > N or i - tmp < 0:
            break
        dp[i] = min(dp[i], dp[i-tmp]+1)
    for j in range(i+1):
        tmp = 9**j
        if tmp > N or i - tmp < 0:
            break
        dp[i] = min(dp[i], dp[i-tmp]+1)

print(dp[N])

Solution (Python):
def ninebeki(n):
    cnt=0
    while n>=9**cnt:
        cnt+=1
    return cnt-1
def sixbeki(n):
    cnt=0
    while n>=6**cnt:
        cnt+=1
    return cnt-1

def resolve():
    n=int(input())
    cnt=0
    q=ninebeki(n)
    r=sixbeki(n)
    l=[9**i for i in range(1,q+1)]
    l+=[6**i for i in range(1,r+1)]
    l.append(1)
    l.sort()
    d=[n for i in range(n+1)]
    d[0]=0
    for c in l:
        for i in range(c,n+1):
            d[i]=min(d[i],d[i-c]+1)
    print(d[n])
resolve()

Solution (Python):
import sys

from collections import deque

from collections import defaultdict

import heapq

import bisect





s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))


def main():
    N = i2n()
    coins = [1]
    d = 6
    while d <= N:
        coins.append(d)
        d *= 6
    d = 9
    while d <= N:
        coins.append(d)
        d *= 9
    q = deque()
    q.append((0, 0))
    s = set((0,))
    while q:
        i, n = q.popleft()
        for j in coins:
            k = i + j
            if k == N:
                print(n+1)
                return
            if k > N:
                continue
            if k in s:
                continue
            q.append((k, n+1))
            s.add(k)
    print(-1)

main()

Solution (Python):
import sys

from collections import deque

from collections import defaultdict

import heapq

import bisect





s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))


def main():
    N = i2n()
    coins = [1]
    d = 6
    while d <= N:
        coins.append(d)
        d *= 6
    d = 9
    while d <= N:
        coins.append(d)
        d *= 9
    q = deque()
    q.append((0, 0))
    s = set((0,))
    while len(q) > 0:
        i, n = q.popleft()
        for j in coins:
            k = i + j
            if k == N:
                print(n+1)
                return
            if k > N:
                continue
            if k in s:
                continue
            q.append((k, n+1))
            s.add(k)
    print(-1)

main()