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())

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

sixes = [pow(6, num) for num in range(1, 10)]
nines = [pow(9, num) for num in range(1, 10)]

for six in sixes:
    for i in range(n + 1):
        if six + i <= n and cnt[i] != float("inf"):
            cnt[six + i] = min(cnt[six + i], cnt[i] + 1)

for nine in nines:
    for i in range(n + 1):
        if nine + i <= n and cnt[i] != float("inf"):
            cnt[nine + i] = min(cnt[nine + i], cnt[i] + 1)

for i in range(n):
    cnt[i + 1] = min(cnt[i + 1], cnt[i] + 1)

print(cnt[n])

Solution (Python):
n = int(input())
dp = [float("Inf")]*(n+1)
for i in range(min(6, n+1)):
    dp[i] = i
for i in range(n):
    for j in range(1,n//6+1):
        if i + 6**j > n:
            break
        dp[i+6**j] = min(dp[i+6**j], dp[i] + 1)
    for j in range(1,n//9+1):
        if i + 9**j > n:
            break
        dp[i+9**j] = min(dp[i+9**j], dp[i] + 1)
print(dp[-1])

Solution (Python):
import sys
from collections import defaultdict
from heapq import heappush, heappop
def input(): return sys.stdin.readline().strip()


def main():
    """
    ６のべき乗しか引き出せない部分問題を考える。
    このとき最適な支払方法は、当然大きい金額を序盤に一気に下ろすこと。
    なのでN円をi円と(N - i)円に分けて片方を6のべき、もう片方を９のべきで支払って
    その合計を見ればよい。

    それぞれの支払い方はすなわち６進数（９進数）展開することに他ならないので
    １円から支払う方法を考えた方が早い。
    """
    N = int(input())
    ans = N
    for i in range(N + 1):
        cnt = 0
        t = 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):
import sys

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def Base(X, n):
    if (int(X/n)):
        return Base(int(X/n), n)+str(X%n)
    return str(X%n)

def main():
    N = ii()
    m = 10**100
    for i in range(N+1):
        a = sum(map(int, Base(i, 6)))
        b = sum(map(int, Base(N-i, 9)))
        m = min(m, a+b)
    print(m)

if __name__ == '__main__':
    main()

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

Solution (Python):
n = int(input())
dp = [float("Inf")]*(n+1)
dp[0] = 0
for i in range(n):
    if dp[i] == float("Inf"):
        pass
    else:
        for j in range(1,n//6+1):
            if i + 6**j > n:
                break
            dp[i+6**j] = min(dp[i+6**j], dp[i] + 1)
        for j in range(1,n//9+1):
            if i + 9**j > n:
                break
            dp[i+9**j] = min(dp[i+9**j], dp[i] + 1)
ans = n
for i in range(max(0, n-5), n+1):
    ans = min(ans, dp[i]+n-i)
print(ans)

Solution (Python):
N = int(input())
inf = float("inf")
dp = [inf for _ in range(N+1)]
l6 = 7
l9 = 6
dp[0] = 0


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

print(dp[N])

Solution (Python):

import sys


def solve(N: int):
    from itertools import takewhile, count
    dp = list(range(N+1))
    for n in (6, 9):
        for m in takewhile(lambda x: x<=N, (n**e for e in count(1))):
            for i in range(m, N+1):
                dp[i] = min(dp[i], dp[i-m]+1)
    return dp[N]



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    print(solve(N))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    
    main()

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

Solution (Python):
import math

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

dp[0] = 0

for i in range(1,N+1):
    A = dp[i-1] + 1
    
    k = int(round(math.log(i, 6), 10))
    B = dp[i - 6 ** k] + 1
    
    k = int(round(math.log(i, 9), 10))
    C = dp[i - 9 ** k] + 1

    dp[i] = min(A,B,C)

print(dp[N])

Solution (Python):
import sys
from functools import lru_cache


sys.setrecursionlimit(500000)


@lru_cache(maxsize=None)
def rec(n):
    if n == 0:
        return 0
    res = n
    i = 1
    while i <= n:
        res = min(res, rec(n - i) + 1)
        i *= 6
    i = 9
    while i <= n:
        res = min(res, rec(n - i) + 1)
        i *= 9
    return res


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

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

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

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

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
  s=n-i
  while s>0:
    cnt+=s%9
    s//=9
  ans = min(ans,cnt)
print(ans)

Solution (Python):
N = int(input())
ans = 10**5

def base(x, n):
  A = 0
  while x != 0:
    A += x % abs(n)
    if n < 0:
      x = - ( (-x)//n )
    else:
      x //= n
  return A

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

print(ans)

Solution (Python):
from collections import defaultdict
import math
N = int(input())
P = defaultdict(int)
def rev(A):
    if A == 0:
        return 0
    elif A in P:
        return P[A]
    else:
        a = int(math.log(A, 9)+10**(-10))
        b = int(math.log(A, 6)+10**(-10))
        if A > 9:
            k = min([rev(A - 9 ** a) + 1, rev(A - 6 ** b) + 1])
            P[A] = k
            return k
        else:
            k = min([rev(A - 9 ** a) + 1, rev(A - 6 ** b) + 1, rev(A - 1) + 1])
            P[A] = k
            return k

print(rev(N))

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

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

print(ans)

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')] * (n + 1)
dp[0] = 0
nums = [1]
i = 1
while 6 ** i <= n:
    nums.append(6 ** i)
    i += 1
i = 1
while 9 ** i <= n:
    nums.append(9 ** i)
    i += 1
nums.sort()
for i in range(n + 1):
    for j in range(len(nums)):
        num = nums[j]
        if i - num >= 0:
            dp[i] = min(dp[i], dp[i - num] + 1)
ans = dp[n]
print(ans)

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

sub=[1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
cost=[0]*(n+1)
for i in range(n+1):
    cost[i]=i
for i in range(n+1):
    for j in range(len(sub)):
        if sub[j]<=i:
            cost[i]=min(cost[i], cost[i-sub[j]]+1)
        else:
            break
print(cost[n])

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

sub=[1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
cost=[0]*(n+1)
for i in range(n+1):
    cost[i]=i
for i in range(n+1):
    for j in range(len(sub)):
        if sub[j]<=i:
            cost[i]=min(cost[i], cost[i-sub[j]]+1)
print(cost[n])

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

sub=[1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
cost=[0]*(n+1)
for i in range(n+1):
    cost[i]=i
for i in range(n+1):
    for j in range(len(sub)):
        if sub[j]<=i:
            cost[i]=min(cost[i], cost[i-sub[j]]+1)
print(cost[n])

Solution (Python):
n=int(input())
ans=n
for n1 in range(n+1):
  n2=n-n1
  cnt1=0
  while n1>0:
    cnt1+=n1%6
    n1=n1//6
  cnt2=0
  while n2>0:
    cnt2+=n2%9
    n2=n2//9
  ans=min(ans,cnt1+cnt2)
print(ans)

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())
L=[1]
now=6
while now<=10**6:
    L.append(now)
    now*=6
now=9
while now<=10**6:
    L.append(now)
    now*=9

dp=[float("INF")]*(N+1)
dp[0]=0
for i in range(1,N+1):
    for x in L:
        if i-x>=0:
            dp[i]=min(dp[i], dp[i-x]+1)
print(dp[N])

Solution (Python):
sub = [1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
N = int(input())

cost = [0] * (N+1)
for i in range(N+1):
    cost[i] = i

for i in range(N+1):
    for j in range(len(sub)):
        if(sub[j] <= i):
            cost[i] = min(cost[i], cost[i-sub[j]] + 1)
print(cost[N])

Solution (Python):
L=[1]
n=int(input())
x = 6
y = 9
while x <= n:
  L.append(x)
  x *= 6
while y <= n:
  L.append(y)
  y *= 9
L.sort()
dp = [float("Inf")]*(n+1)
dp[0] = 0
for i in range(n+1):
  for j in L:
    if i+j <= n:
      dp[i+j] = min(dp[i+j],dp[i]+1)
    else:
      break
print(dp[n])

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

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

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

    k = 1
    while k <= n:
        dp[i] = min(dp[i], dp[i-k]+1)
        k *= 9

print(dp[n])

Solution (Python):
L = [1]
n = int(input())
x = 6
y = 9
while x <= n:
    L.append(x)
    x *= 6
while y <= n:
    L.append(y)
    y *= 9
L.sort()
dp = [float("Inf")]*(n+1)
dp[0] = 0
for i in range(n+1):
    for j in L:
        if i+j <= n:
            dp[i+j] = min(dp[i+j],dp[i]+1)
        else:
            break
print(dp[n])

Solution (Python):
L = [1]
n = int(input())
x = 6
y = 9
while x <= n:
    L.append(x)
    x *= 6
while y <= n:
    L.append(y)
    y *= 9
L.sort()
dp = [float("Inf")]*(n+1)
dp[0] = 0
for i in range(n+1):
    for j in L:
        if i+j <= n:
            dp[i+j] = min(dp[i+j],dp[i]+1)
        else:
            break
print(dp[n])

Solution (Python):
N = int(input())
INF = 10 ** 9
dp = [INF] * (N + 1)
dp[0] = 0
M = set()
M.add(1)
i = 1
while True:
    if 6 ** i > N:
        break
    M.add(6 ** i)
    i += 1
i = 1
while True:
    if 9 ** i > N:
        break
    M.add(9 ** i)
    i += 1
for i in range(N):
    for m in M:
        if i + m > N:
            continue
        dp[i + m] = min(dp[i + m], dp[i] + 1)
print(dp[N])

Solution (Python):

N = int(input())
dp = [N for i in range(N+1)]
dp[0] = 0
Y = [1] + [6**i for i in range(1, 10) if 6**i <= N] + [9**i for i in range(1, 10) if 9**i <= N]
Y = sorted(Y)
for i in range(1, N+1):
    for y in Y:
        if i-y < 0:
            break
        dp[i] = min(dp[i], dp[i-y]+1)
print(dp[N])

Solution (Python):
N = int(input())
ans = 10**13
Y = [9**i for i in range(1, 10)] + [6**i for i in range(1, 10)]
Y = sorted(Y, reverse=True)
for i in range(N+1):
    tmp = 0
    n = N-i
    for j in range(10, -1, -1):
        if i // 9**j > 0:
            tmp += i // 9**j
            i %= 9**j
    for j in range(10, -1, -1):
        if n // 6**j > 0:
            tmp += n // 6**j
            n %= 6**j
        

        
    ans = min(ans, tmp)

print(ans)

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

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

'''
もらうDP
for i in range(1, N + 1):
    pow6 = 1
    while pow6 <= i:
        dp[i] = min(dp[i], dp[i - pow6] + 1)
        pow6 *= 6

    pow9 = 1
    while pow9 <= i:
        dp[i] = min(dp[i], dp[i - pow9] + 1)
        pow9 *= 9
'''

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])

Solution (Python):
n = int(input())
INF = float('inf')
L = [1]
for x in (6, 9):
    i = 1
    while x ** (i + 1) < 10 ** 6:
        L.append(x ** i)
        i += 1
L.sort(reverse=True)
dp = [INF] * (n + 1)
dp[0] = 0
for m in L:
    for i in range(n+1):
        if dp[i] != INF:
            if i + m <= n:
                dp[i+m] = min(dp[i] + 1, dp[i+m])
print(dp[-1])

Solution (Python):
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

curr=[1, 6, 36, 216, 1296, 7776, 46656, 279936, 9, 81, 729, 6561, 59049, 531441]
curr.sort()


N=II()
DP=[10000000]*(N+1)
DP[N]=0

for i in reversed(range(0, N+1)):
    for c in curr:
        if i-c >= 0: DP[i-c] = min(DP[i]+1, DP[i-c])
print(DP[0])

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

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

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

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

price = {1}
for i in range(1, 100):
    tmp = 6**i
    if tmp > 10**5:
        break
    price.add(tmp)

for i in range(1, 100):
    tmp = 9**i
    if tmp > 10**5:
        break
    price.add(tmp)

price = list(price)
price.sort(reverse=True)

INF = 1 << 60

dp = [INF] * 2 * 10**5
dp[0] = 0
dp[1] = 1

for i in range(n + 1):
    for p in price:
        dp[i + p] = min(dp[i] + 1, dp[i + p])

print(dp[n])

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

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

Solution (Python):
n=int(input())
dp=[99]*5000000
dp[0]=0
for i in range(n):
    for j in range(8):
        dp[i+6**j]=min(dp[i+6**j],dp[i]+1)
        dp[i+9**j]=min(dp[i+9**j],dp[i]+1)
print(dp[n])

Solution (Python):
n=int(input())
a=[6**i for i in range(10)]+[9**i for i in range(10)]
dp=list(range(10**5+1))
dp[1]=1
for i in range(n):
    for j in a:
        if i+j<10**5+1:
            dp[i+j]=min(dp[i+j],dp[i]+1)
print(dp[n])

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
N = int(input())
dp = [-1] * (N + 1)

def rec(n):
    if n == 0:
        return 0
    if dp[n] != -1:
        return dp[n]
    res = n
    i = 0
    while n >= 6 ** i:
        pow6 = 6 ** i
        res = min(res, rec(n - pow6) + 1)
        i += 1
    j = 0
    while n >= 9 ** j:
        pow9 = 9 ** j
        res = min(res, rec(n - pow9) + 1)
        j += 1
    dp[n] = res
    return res
print(rec(N))

Solution (Python):
dp = [999999] * 100100
n = int(input())
dp[0] = 0
for i in range(0, 100010):
    dp[i+1] = min(dp[i+1], dp[i] + 1)
    for j in range(1,100):
        c = i + 6**j
        if (c) > 100000:
            break
        dp[c] = min(dp[c], dp[i] + 1)

    for j in range(1,100):
        c = i + 9**j
        if (c) > 100000:
            break
        dp[c] = min(dp[c], dp[i] + 1)


print(dp[n])

Solution (Python):
n = int(input())
l = [1]
c = 1
while(6**c <= 100000):
    l.append(6**c)
    c += 1
c = 1
while(9**c <= 100000):
    l.append(9**c)
    c += 1
l.sort()
dp = [100001 for _ in range(n+1)]
dp[0] = 0
for i in range(len(l)):
    for j in range(l[i],n+1):
        dp[j] = min(dp[j],dp[j - l[i]]+1)
print(dp[n])

Solution (Python):
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    M = [1]
    for i in range(1, 12):
        if pow(6, i) > N: break
        M.append(pow(6, i))
    for i in range(1, 10):
        if pow(9, i) > N: break
        M.append(pow(9, i))
    M.sort()

    DP = [100000] * (N + 1)
    DP[N] = 0
    for i in reversed(range(N + 1)):
        if DP[i] < 100000:
            for m in M:
                if i - m >= 0: DP[i-m] = min(DP[i-m], DP[i] + 1)
    print(DP[0])

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
def main():
    n = int(input())
    C = [1, ]
    c = 6
    while c < 100000:
        C.append(c)
        c *= 6
    c = 9
    while c < 100000:
        C.append(c)
        c *= 9
    INF = float('inf')
    dp = [INF] * (n + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        C_filtered = [c for c in C if c <= i]
        dp[i] = min([dp[i - c] + 1 for c in C_filtered])
    print(dp[n])
if __name__ == '__main__':
    main()

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

dp = [float('inf')] * (N+1)
dest = [1]
dp[0] = 0
for i in range(1,10):
    if 6 ** i <= N:
        dp[6 ** i] = 1
        dest.append(6 ** i)
    else:
        break
    if 9 ** i <= N:
        dp[9 ** i] = 1
        dest.append(9 ** i)

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

Solution (Python):
n = int(input())
dp = [10*9]*100001
dp[0] = 0
for i in range(1, n+1):
  c6 = 0
  c9 = 0
  while 6 ** c6 <= i:
    c6 += 1
  while 9 ** c9 <= i:
    c9 += 1
  dp[i] = min(dp[i-1]+1, dp[i-6**(c6-1)]+1, dp[i-9**(c9-1)]+1)

print(dp[n])

Solution (Python):



def main():
    N = int(input())
    INF = 10**10
    dp = [INF] * (N+1)
    dp[0] = 0
    bk = set([1])
    for i in range(100):
        if pow(6,i)>N:
            break
        bk.add(pow(6,i))
    for i in range(100):
        if pow(9,i)>N:
            break
        bk.add(pow(9,i))

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

if __name__ == '__main__':
    main()

Solution (Python):
import sys
n = int(input())
INF = 10*n
dp = [INF]*(n+1)
dp[0] = 0
for i in range(1, n+1):
    tmp = dp[i-1] + 1
    for j in range(10):
        if i-6**j<0:
            break
        tmp = min(tmp, dp[i-6**j] + 1)
    for j in range(10):
        if i-9**j<0:
            break
        tmp = min(tmp, dp[i-9**j] + 1)
    dp[i] = tmp
print(dp[n])

Solution (Python):
import sys
n = int(input())
INF = 10*n
dp = [INF]*(n+1)
dp[0] = 0
for i in range(1, n+1):
    tmp = dp[i-1] + 1
    for j in range(10):
        if i-6**j<0:
            break
        tmp = min(tmp, dp[i-6**j] + 1)
    for j in range(10):
        if i-9**j<0:
            break
        tmp = min(tmp, dp[i-9**j] + 1)
    dp[i] = tmp
print(dp[n])

Solution (Python):
n=int(input())
l=[1,6,36,6**3,6**4,6**5,6**6,9,9**2,9**3,9**4,9**5]
l.sort(reverse=True)
dp=[float("inf")]*1000000
dp[0]=0
for i in range(1,n+1):
    for j in l:
        if i-j>=0:
            dp[i]=min(dp[i],dp[i-j]+1)
print(dp[n])

Solution (Python):
import queue

n=int(input())

sixexp=[6**i for i in range(1,7)]
nineexp=[9**i for i in range(1,6)]

lis=[1]+sixexp+nineexp

q=queue.Queue()

numlist=[0 for i in range (n+1)]

c=0
while c!=n:
    for i in lis:
        if c+i<=n:
            if numlist[c+i]==0:
                q.put(c+i)
                numlist[c+i]=numlist[c]+1
    c=q.get()
print(numlist[n])

Solution (Python):
sixexp=[6**i for i in range(1,7)]
nineexp=[9**i for i in range(1,6)]
lis=[1]+sixexp+nineexp

n=int(input())

dp=[1000000 for i in range (n+1)]
dp[0]=0

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

print(dp[n])

Solution (Python):
sixexp=[6**i for i in range(1,7)]
nineexp=[9**i for i in range(1,6)]
lis=[1]+sixexp+nineexp

n=int(input())

dp=[1000000 for i in range (n+1)]
dp[0]=0

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

print(dp[n])

Solution (Python):
sixexp=[6**i for i in range(1,7)]
nineexp=[9**i for i in range(1,6)]
lis=[1]+sixexp+nineexp

n=int(input())

dp=[1000000 for i in range (n+1)]
dp[0]=0

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

print(dp[n])

Solution (Python):
sixexp=[6**i for i in range(1,7)]
nineexp=[9**i for i in range(1,6)]
lis=[1]+sixexp+nineexp

n=int(input())

F=[0,1]

for i in range(2,n+1):
    dplis=[]
    for j in lis:
        if i-j>=0:
            dplis.append(F[i-j]+1)
    F.append(min(dplis))

print(F[n])

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

lis=[]

temp=6
while temp<=N:
    lis.append(temp)
    temp*=6

temp=9
while temp<=N:
    lis.append(temp)
    temp*=9

lis.sort(reverse=True)

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


for item in lis:
    for i in range(N+1):
        if dp[i]!=10**9:
            if i+item<=N:
                dp[i+item]=min(dp[i]+1,dp[i+item])

ans=10**10
for index,item in enumerate(dp):
    ans=min(ans,item+N-index)
print(ans)

Solution (Python):
from bisect import bisect_right

n = int(input())

six = [0] + [6**i for i in range(1,8)]
nine = [0] + [9**i for i in range(1,7)]

dp = [float("inf")] * (n+1)
dp[0] = 0
for i in range(1, n+1):
    dp[i] = dp[i-1] + 1
    j = bisect_right(six, i) - 1
    if j: dp[i] = min(dp[i], dp[i-six[j]] + 1)
    k = bisect_right(nine, i) - 1
    if k: dp[i] = min(dp[i], dp[i-nine[k]] + 1)

print(dp[-1])

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

sixs = [6]
while sixs[-1] * 6 <= n:
    sixs.append(sixs[-1] * 6)

nines = [9]
while nines[-1] * 9 <= n:
    nines.append(nines[-1] * 9)

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

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

    for nine in nines:
        if i - nine >= 0:
            dp[i] = min(dp[i], dp[i-nine] + 1)

print(dp[-1])

Solution (Python):
N = int(input())
dp = [i for i in range(N+1+9**5)]
for i in range(N):
  dp[i+1] = min(dp[i+1], dp[i] + 1)
  for j in range(1, 7):
    dp[i+6**j] = min(dp[i+6**j], dp[i] + 1)
  for k in range(1, 6):
    dp[i+9**k] = min(dp[i+9**k], dp[i] + 1)
    
print(dp[N])

Solution (Python):
from collections import deque
n = int(input())
q = deque([])
now = 0
reach = [0]*100001
lis = []
for i in range(6):
    lis.append(6**(i+1))
for i in range(5):
    lis.append(9**(i+1))
lis.append(1)
lis = sorted(lis)
q.append(0)
ans = 0
while q:
    if ans == 1:
        break
    x = q.popleft()
    
    for y in lis:
        if x + y < n:
            if  reach[x+y] == 0:
                q.append(x+y)
                reach[x+y] = reach[x]+1
            
        elif x + y == n:
            reach[x+y] = reach[x]+1
            ans = 1
            break
print(max(reach))

Solution (Python):
def f(yen, coin, cnt=0):
    while yen > 0: yen,r=divmod(yen,coin); cnt+=r
    return cnt

ans = n = int(input())
for yen6 in range(0, n+1):
    ans = min(ans, f(n-yen6, 9, f(yen6, 6)))
print(ans)

Solution (Python):
def f(yen, coin, cnt=0):
    while yen > 0: cnt += yen % coin; yen //= coin
    return cnt

ans = n = int(input())
for yen6 in range(0, n+1):
    ans = min(ans, f(n-yen6, 9, f(yen6, 6)))
print(ans)

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

def f(yen, p):
    c = p
    while yen >= c:
        dp[yen] = min(dp[yen], dp[yen-c] + 1)
        c *= p

for yen in range(6, n+1):
    f(yen, 6)
    f(yen, 9)
print(dp[n])

Solution (Python):
coin = [1,
6,6**2,6**3,6**4,6**5,6**6,
9,9**2,9**3,9**4,9**5]
n = int(input())
inf = 10**9
dp = [inf]*(n+1)
dp[0] = 0
for c in coin:
    for yen in range(c, n+1):
        dp[yen] = min(dp[yen], dp[yen-c] + 1)
print(dp[n])

Solution (Python):
from bisect import bisect_right
n = int(input())
MX = 100010
dp = [float('inf') for _ in range(MX)]
dp[0] = 0
pow_6, pow_9 = [6], [9]
while True:
    flg = False
    if pow_6[-1]*6 <= MX:
        pow_6.append(pow_6[-1]*6)
        flg = True
    if pow_9[-1]*9 <= MX:
        pow_9.append(pow_9[-1]*9)
        flg = True
    
    if flg == False:
        break

for i in range(1, MX):
    tmp = [1]
    if i >= 6:
        x = bisect_right(pow_6, i)
        tmp.append(pow_6[x-1])
    if i >= 9:
        y = bisect_right(pow_9, i)
        tmp.append(pow_9[y-1])
    for t in tmp:
        dp[i] = min(dp[i], dp[i-t]+1)
print(dp[n])

Solution (Python):
N = int(input())
ans = float('inf')
ls = []
l = [1]
tmp = 6
while tmp <= 100000:
    l += [tmp]
    tmp *= 6
tmp = 9
while tmp <= 100000:
    l += [tmp]
    tmp *= 9

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

Solution (Python):
N = int(input())
ans = float('inf')
ls = []
l = [1]
tmp = 6
while tmp <= 100000:
    l += [tmp]
    tmp *= 6

tmp = 9
while tmp <= 100000:
    l += [tmp]
    tmp *= 9

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

print(dp[N])

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

def drawal(x):
  if(x <= 5):
    return x
  elif(6<= x and x < 9):
    return x- 5
  elif(9<= x and x < 15):
    return x- 8
  else:
    def drawal9(y):
      i = 0
      while 9** (i+ 1)<= y:
        i+= 1
      return drawal(y- 9** i)+ 1
    def drawal6(z):
      i = 0
      while 6** (i+ 1)<= z:
        i+= 1
      return drawal(z- 6** i)+ 1
    return min(drawal9(x), drawal6(x))

print(drawal(N))

Solution (Python):
n=int(input())
h=[1,6,6**2,6**3,6**4,6**5,6**6,9,9**2,9**3,9**4,9**5,9**6]
dp=[10**9]*(n+1)

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

Solution (Python):

import sys
input = sys.stdin.readline









N = int(input())


dp = [0]*(N+100010)

for i in range(100000):
    dp[i] = 10**10



for i in range(100001,N+100010):
    dp[i] = min(dp[i-1] + 1,
                dp[i-6] + 1,
                dp[i-9] + 1,
                dp[i-36] +1,
                dp[i-81] + 1,
                dp[i-216] + 1,
                dp[i-729] + 1,
                dp[i-1296] + 1,
                dp[i-6561] + 1,
                dp[i-7776] + 1,
                dp[i-46656] + 1,
                dp[i-59049] + 1)
 
print(dp[N+100000])

Solution (Python):
import sys
sys.setrecursionlimit(10**9)


n=int(input())



memo=[-1]*(n+1)
memo[0]=0

def fuck(x):
    
    if memo[x]!=-1:
        return memo[x]
    else:
        tmp=10**9
        
        i=1
        while 6**i<=x:
            tmp=min(fuck(x-6**i),tmp)
            i+=1
        
        i=1
        while 9**i<=x:
            tmp=min(fuck(x-9**i),tmp)
            i+=1
        
        tmp=min(tmp,fuck(x-1))
        memo[x]=tmp+1
        
        return tmp+1
fuck(n)

print(memo[-1])

Solution (Python):

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
answer = N

for i in range(N+1):
    temp = 0
    six_pay = i
    while six_pay:
        temp += six_pay%6
        six_pay //= 6
    nine_pay = N - i
    while nine_pay:
        temp += nine_pay%9
        nine_pay //= 9
    if temp < answer:
        answer = temp

print(answer)

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

Solution (Python):
import sys
import math
N = int(sys.stdin.readline().rstrip())







    






money = [1]
for i in range(20):
    if 100000 >= 6**i:
        money.append(6**i)
    if 100000 >= 9**i:
        money.append(9**i)

money = sorted(money)[::-1]


dp = [[10**18] * (N + 1) for _ in range(len(money) + 1)]
dp[0][0] = 0

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

print(dp[len(money)][N])

Solution (Python):
import sys
import math
N = int(sys.stdin.readline().rstrip())







    






money = [1]
for i in range(20):
    if 100000 >= 6**i:
        money.append(6**i)
    if 100000 >= 9**i:
        money.append(9**i)


dp = [[10**18] * (N + 1) for _ in range(len(money) + 1)]
dp[0][0] = 0

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

print(dp[len(money)][N])

Solution (Python):

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
answer = N

for i in range(N+1):
    temp = 0
    six_pay = i
    while six_pay:
        temp += six_pay%6
        six_pay //= 6
    nine_pay = N - i
    while nine_pay:
        temp += nine_pay%9
        nine_pay //= 9
    if temp < answer:
        answer = temp

print(answer)

Solution (Python):

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


N = ir()
INF = 10 ** 8
dp = [INF] * (N+1)
dp[0] = 0
for i in range(5, 0, -1):
    num = 9 ** i
    for j in range(N):
        if j+num <= N:
            dp[j+num] = min(dp[j+num], dp[j]+1)

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

num = 1
for j in range(N):
    dp[j+num] = min(dp[j+num], dp[j]+1)

answer = dp[N]
print(answer)