Problem:


Score : 300 points

Problem Statement

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

1 yen (the currency of Japan)

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

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

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

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

Constraints

1 \leq N \leq 100000

N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

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

Sample Input 1

127

Sample Output 1

4

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

Sample Input 2

3

Sample Output 2

3

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

Sample Input 3

44852

Sample Output 3

16



Sample input:
127


Sample output:
4

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    mon6=[6]
    mon9=[1]
    for i in range(5):
        mon6.append(6*mon6[i])
        mon9.append(9*mon9[i])
    mon=mon6+mon9
    mon.sort()
    
    
    inf=10**9
    dp=[[inf]*(n+1) for i in range(13)]
    
    for i in range(13):
      dp[i][0]=0
    for i in range(12):
        for j in range(1,n+1):
            if j-mon[i]>=0:
                dp[i+1][j]=min(dp[i+1][j-mon[i]]+1,dp[i][j])
            else:
                dp[i+1][j]=dp[i][j]
    print(dp[-1][-1]) 
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

dp = [100000] * (10**6)
dp[0] = 0

for n in range(N):
  count = 1
  while(True):
    if count > N:
      break

    dp[n+count] = min(dp[n+count], dp[n]+1)
    count *= 6

  count = 1
  while(True):
    if count > N:
      break

    dp[n+count] = min(dp[n+count], dp[n]+1)
    count *= 9

print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())

dp = [10000] * (N+1)

dp[0] = 0

for n in range(N+1):
  count = 1
  while(True):
    if count > N:
      break

    if n - count < 0:
      break

    dp[n] = min(dp[n], dp[n-count]+1)
    count *= 6

  count = 1
  while(True):
    if count > N:
      break

    if n - count < 0:
      break

    dp[n] = min(dp[n], dp[n-count]+1)
    count *= 9

print(dp[N])

Submission status: Accepted

Solution code:
from math import log
N = int(input())
dp = [0] * (10**5+1)
dpl = set()
a = 1
b = 1
while True:
    if a > 10**5:
        break
    a *= 6
    dpl.add(a)
while True:
    if b > 10**5:
        break
    b *= 9
    dpl.add(b)

for i in range(1, 10**5+1):
    if i < 6:
        dp[i] = i
        continue
    log6 = log(i, 6)
    log9 = log(i, 9)
    l = set(map(float, range(1, 20)))
    # 6の乗数、9の乗数の場合は1でdpを埋める
    if log6 in l:
        dp[i] = 1
    elif log9 in l:
        dp[i] = 1
    # それ以外の数値は各6, 9の乗数を引いた値から最も小さい数で埋める
    else:
        minl = [dp[i-d]+1 for d in dpl if i-d >= 0]
        if minl:
            dp[i] = min(minl)

print(dp[N])

Submission status: Accepted

Solution code:
n=int(input())
a=n
for i in range(n+1):
  c,j=0,n-i
  while i: c+=i%6; i//=6
  while j: c+=j%9; j//=9
  a=min(a,c)
print(a)

Submission status: Accepted

Solution code:
n=int(input())
def f(k,m):
  c=0
  while k: c+=k%m; k//=m
  return c
a=n
for i in range(n+1):
  a=min(a,f(i,6)+f(n-i,9))
print(a)

Submission status: Accepted

Solution code:
s={int(input())}
def f(k,m):
  p=1;
  while p*m<=k: p*=m
  return p
a=0
while all(s):
  s={i-f(i,6) for i in s}|{i-f(i,9) for i in s}
  a+=1
print(a)

Submission status: Accepted

Solution code:
n=int(input())

dp=[float('inf')]*(n+1)
dp[0]=0
moneys=[6,9]
for money in range(n+1):
    if dp[money]!=float('inf'):

        for i in moneys:
            cnt=0
            while money+i**cnt<=n:
                dp[money+i**cnt]=min(dp[money]+1,dp[money+i**cnt])
                cnt+=1
print(dp[-1])

Submission status: Accepted

Solution code:
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda x: [na() for _ in range(x)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda x: [ns() for _ in range(x)]
nas = lambda: stdin.readline().split()

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

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

print(dp[n])

Submission status: Accepted

Solution code:
N = int(input())
n6 = 1
n9 = 1
li = []
while 9**n9 <= N:
    li.append(9**n9)
    n9 += 1
while 6**n6 <= N:
    li.append(6**n6)
    n6 += 1

li.sort()
INF = 10**10
# 1円の場合はね
dp = [[i for i in range(N+1)] for i in range(len(li) + 1)]
dp = [i for i in range(N+1)]


for i,l in enumerate(li):
    for j in range(N+1):
        if j+l > N : continue
        dp[j+l] = min(dp[j+l], dp[j]+1)
print(dp[N])

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']

mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

n=I()
N=10**5+1
dp=[inf]*(N)
dp[0]=0
six=[6**i for i in range(1,7)]
nine=[9**i for i in range(6)]
a=six+nine
for i in range(n):
    for j in a:
        if i+j<N:
            dp[i+j]=min(dp[i+j],dp[i]+1)

print(dp[n])

Submission status: Accepted

Solution code:
N = int(input())
dp = [0] * (N+1)
import math
import heapq
if N != 59049:
    for i in range(1,N+1):
        A = []
        heapq.heapify(A)
        k = dp[i-1] +1
        heapq.heappush(A,k)
        s6 = int(math.log(i,6))
        s9 = int(math.log(i,9))
        for j in range(1,s6+1):
            d = i - 6**j
            l = dp[d] + 1
            heapq.heappush(A,l)
        for j in range(1,s9+1):
            dl = i - 9**j
            lu = dp[dl] + 1
            heapq.heappush(A,lu)
        dp[i] = heapq.heappop(A)
    print(dp[N])
else:
    print(1)

Submission status: Accepted

Solution code:
N = int(input())
inf = float('inf')
dp = [inf] * 100001
dp[0] = 0
for n in range(1, 100001):
    power = 1
    while power <= n:
        dp[n] = min(dp[n], dp[n - power] + 1)
        power *= 6
    power = 1
    while power <= n:
        dp[n] = min(dp[n], dp[n - power] + 1)
        power *= 9

# print(dp)
print(dp[N])

Submission status: Accepted

Solution code:
n=int(input())
ans=n
for i in range(n+1):
    buf=0
    j=n-i
    while i>0:
        i0=i%6
        i=(i-i0)//6
        buf+=i0
    while j>0:
        j0=j%9
        j=(j-j0)//9
        buf+=j0
    if buf<ans:
        ans=buf
print(ans)

Submission status: Accepted

Solution code:
list1=[6**i for i in range(1,7)]
list2=[9**i for i in range(1,6)]
data=[1]
data+=list1+list2
data.sort()
N=int(input())
count=0
dp=[10**7 for i in range(0,N+1)]
dp[0]=0
dp[1]=1
for i in range(2,N+1):
    max=0
    start=0
    end=11
    while end-start>1:
        test=(start+end)//2
        if N>=data[test]:
            start=test
        else:
            end=test
    if N>=data[end]:
        max=end
    else:
        max=start
    dp[i]=1+min(dp[i-data[j]] for j in range(0,max+1))
print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())
DP = [100000000] * (N+1)
DP[0] = 0
for i in range (N):
    DP[i + 1] = DP[i] + 1
    for j in range (8):
        if 6**j <= i + 1:
            DP[i + 1] = min(DP[i + 1],DP[i + 1 - 6**j] + 1)
    for j in range (8):
        if 9**j <= i + 1:
            DP[i + 1] = min(DP[i + 1],DP[i + 1 - 9**j] + 1)
print(DP[N])

Submission status: Accepted

Solution code:
N = int(input())
r = N

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

Submission status: Accepted

Solution code:
INF = 10 ** 20
 
N = int(input())
coin_list = [1] + [6**i for i in range(1, 7)] + [9**i for i in range(1, 6)]
dp = [INF]*(N+1)
dp[0] = 0
 
for i in range(1,N+1):
	for coin in coin_list:
	    if i-coin >= 0: dp[i] = min(dp[i], dp[i-coin]+1)
 
print(dp[N])

Submission status: Accepted

Solution code:
INF = 10 ** 20
 
N = int(input())
coin_list = [1] + [6**i for i in range(1, 7)] + [9**i for i in range(1, 6)]
dp = [INF]*(N+1)
dp[0] = 0
 
for coin in coin_list:
    for i in range(coin,N+1):
        dp[i] = min(dp[i], dp[i-coin]+1)
 
print(dp[N])

Submission status: Accepted

Solution code:
INF = 10 ** 20

N = int(input())
coin_list = [1] + [6**i for i in range(1, 7)] + [9**i for i in range(1, 6)]
dp = [INF]*(N+1)
dp[0] = 0
 
for coin in coin_list:
    for i in range(coin,N+1):
        dp[i] = min(dp[i], dp[i-coin]+1)
 
print(dp[N])

Submission status: Accepted

Solution code:
'''
DPで解く
操作を以下2パターンとして考える
 6 ** 0(= 1), 6 ** 1, 6 ** 2...
 9 ** 0(= 1), 9 ** 1, 9 ** 2...
'''

N = int(input())

# DPテーブル
dp = [10 ** 5] * (N + 1)

# 6 or 9 の累乗のリスト
six = []
c = 0
while True:
    w = 6 ** c
    if w > N:
        break
    six.append(w)
    c += 1
nine = []
c = 0
while True:
    w = 9 ** c
    if w > N:
        break
    nine.append(w)
    c += 1

# 初期値
dp[0] = 0

# ループ
for i in range(N + 1):
    # 6の累乗を引き出すケース
    for s in six:
        if i + s > N:
            break
        dp[i + s] = min(dp[i + s], dp[i] + 1)
    # 9の累乗を引き出すケース
    for n in nine:
        if i + n > N:
            break
        dp[i + n] = min(dp[i + n], dp[i] + 1)

# 解を出力
print(dp[N])

Submission status: Accepted

Solution code:
n = int(input())

import sys
sys.setrecursionlimit(999999999)
from functools import lru_cache
@lru_cache(maxsize=32)
def solve(cnt,nokori):
    if nokori<6:
        return cnt+nokori

    for six in range(10,-1,-1):
        if 6**six <= nokori:
            break
    for nine in range(10,-1,-1):
        if 9**nine <= nokori:
            break

    res1 = solve(cnt+1,nokori-6**six)
    if nine != 0:
        res2 = solve(cnt+1,nokori-9**nine)
    else:
        res2=10**9

    return min([res1,res2])

print(solve(0,n))

Submission status: Accepted

Solution code:
n=int(input())

def digit(n,m):
    a=n
    _list = []
    while True:
        _list.append(a%m)
        a=a//m
        if a==0:
            break
    return sum(_list)

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

Submission status: Accepted

Solution code:
n=int(input())
maxn=110000
dp=[n for i in range(maxn)] #n円のお金は、最悪全部１円玉でn枚でok
dp[0]=0
for i in range(n): #0-(n-1)円まで
    pow6=1
    while i+pow6<=n:
        dp[i+pow6]=min(dp[i+pow6],dp[i]+1)
        pow6*=6
    pow9=1
    while i+pow9<=n:
        dp[i+pow9]=min(dp[i+pow9],dp[i]+1)
        pow9*=9
print(dp[n])

Submission status: Accepted

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

n=int(input())
maxn=110000
memo=[-1 for i in range(maxn)]
def rec(n):
    if n==0:
        return 0
    if memo[n]!=-1:
        return memo[n]
    res=n
    i=1
    while i<=n:
        res=min(res,rec(n-i)+1)
        i*=6
    j=1
    while j<=n:
        res=min(res,rec(n-j)+1)
        j*=9
    memo[n]=res
    return memo[n]
print(rec(n))
#print(memo)

Submission status: Accepted

Solution code:
N = int(input())

table = [0] * (N + 1)
s = {6 ** i for i in range(7) if 6 ** i <= N} | {9 ** i for i in range(6) if 9 ** i <= N}
for i in range(1, N + 1):
    table[i] = min(table[i - j] for j in s if i - j >= 0) + 1
print(table[N])

Submission status: Accepted

Solution code:
C=[]
for i in range(1,100):
    if 6**i<=10**5:
        C.append(6**i)
for i in range(1,100):
    if 9**i<=10**5:
        C.append(9**i)
        
N=int(input())
dp=[i for i in range(N+1)]
for c in C:
    for i in range(N+1):
        if i-c>=0:
            dp[i]=min(dp[i],dp[i-c]+1)
print(dp[N])

Submission status: Accepted

Solution code:
N=int(input())
res=N
for i in range(N+1):
  cc=0
  t=i
  while t>0:
    cc+=t%6
    t=t//6
  t=N-i
  while t>0:
    cc+=t%9
    t=t//9
  if res>cc:
    res=cc
import math
print(math.floor(res))

Submission status: Accepted

Solution code:
n = int(input())
dp = [1000000]*(n+1)
dp[0] = 0
#6,9,36,81,216,729,1296,6561,7776,46656,59049
for i in range(1,n+1):
    if i >= 1:
        dp[i] = min(dp[i],dp[i-1]+1)
    if i >= 6:
        dp[i] = min(dp[i],dp[i-6]+1)
    if i >= 9:
        dp[i] = min(dp[i],dp[i-9]+1)
    if i >= 36:
        dp[i] = min(dp[i],dp[i-36]+1)
    if i >= 81:
        dp[i] = min(dp[i],dp[i-81]+1)
    if i >= 216:
        dp[i] = min(dp[i],dp[i-216]+1)
    if i >= 729:
        dp[i] = min(dp[i],dp[i-729]+1)
    if i >= 1296:
        dp[i] = min(dp[i],dp[i-1296]+1)
    if i >= 6561:
        dp[i] = min(dp[i],dp[i-6561]+1)
    if i >= 7776:
        dp[i] = min(dp[i],dp[i-7776]+1)
    if i >= 46656:
        dp[i] = min(dp[i],dp[i-46656]+1)
    if i >= 59049:
        dp[i] = min(dp[i],dp[i-59049]+1)
print(dp[-1])

Submission status: Accepted

Solution code:
import bisect
from collections import defaultdict
dd = defaultdict(int)

N=int(input())

a1=[1]
p=1
for i in range(100):
    p*=6
    if p>N:
        break
    a1.append(p)
    
p=1
a2=[1]
for i in range(100):
    p*=9
    if p>N:
        break
    a2.append(p)
    

def rep(NN):
    if dd[NN]!=0:
        return dd[NN]
    if NN==0:
        return 0
    x1=bisect.bisect_right(a1,NN)
    x2=bisect.bisect_right(a2,NN)
    dd[NN]=min(rep(NN-a1[x1-1]), rep(NN-a2[x2-1]))+1
    return dd[NN]
    
rep(N)
print(dd[N])

Submission status: Accepted

Solution code:
n = int(input())

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

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

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

print(dp[n])

Submission status: Accepted

Solution code:
#標準入力を高速に
import sys 
input = sys.stdin.readline

#main関数(若干早くなる)
def main():
    N = int(input())
    INF = float("inf")
    #dp[i]...i円を引き出すのに必要な最小回数
    dp = [INF]*(N+1)
    dp[0] = 0

    #配るDP
    while dp[N] == INF:
        for i in range(N):
            if dp[i] != INF:
                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
                k = 1
                while i+9**k <= N:
                    dp[i+9**k] = min(dp[i]+1, dp[i+9**k])
                    k += 1

    print(dp[N])
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
N = int(input())
dp=[100000]*(100000+1)
dp[0]=0
dp[1:5]=range(1,6)
k9=0
k6=0
for n in range(6,N+1):
  while n//(9**k9)>=9:
    k9+=1
  while n//(6**k6)>=6:
    k6+=1
  dp[n]=min(dp[n],dp[n-6**k6]+1,dp[n-9**k9]+1,dp[n-1]+1)
print(dp[N])

Submission status: Accepted

Solution code:
import math
N = int(input())
dp=[100000]*(100000+1)
dp[0]=0
dp[1:5]=range(1,6)
dp[6:9]=range(1,4)
k9=0
k6=0
for n in range(9,N+1):
  while n//(9**k9)>=9:
    k9+=1
  while n//(6**k6)>=6:
    k6+=1
  dp[n]=min(dp[n],dp[n-6**k6]+1,dp[n-9**k9]+1,dp[n-1]+1)
print(dp[N])

Submission status: Accepted

Solution code:
import math
N = int(input())
dp=[100000]*(100000+1)
dp[0]=0
dp[1:5]=range(1,6)
dp[6:9]=range(1,4)
for n in range(9,N+1):
  k9=0
  k6=0
  while n//(9**k9)>=9:
    k9+=1
  while n//(6**k6)>=6:
    k6+=1
  dp[n]=min(dp[n],dp[n-6**k6]+1,dp[n-9**k9]+1,dp[n-1]+1)
print(dp[N])

Submission status: Accepted

Solution code:
N=int(input())
l=[1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
h=[None]*100001
h[0]=0
k=[0]
c=1
while None in h:
    t=[]
    for i in k:
        for j in l:
            if i+j>100000:
                break
            if h[i+j]==None:
                h[i+j]=c
                t.append(i+j)
    k=t
    c+=1
print(h[N])

Submission status: Accepted

Solution code:
# dpテーブル用意: Nの最大値分まで計算できるように確保
dp = [float('INF')] * (100000*2)
dp[0] = 0

N = int(input())

# 配るdp
for i in range(N+1):
    # 1円更新
    dp[i+1] = min(dp[i+1], dp[i]+1)
    
    # 6の累乗群
    for j in range(1, 7):
        dp[i+(6**j)] = min(dp[i+(6**j)], dp[i]+1)
    
    # 9の累乗群
    for k in range(1, 6):
        dp[i+(9**k)] = min(dp[i+(9**k)], dp[i]+1)


print(dp[N])

Submission status: Accepted

Solution code:
# 貪欲的だが「6^i円で払う分」と「9^i円で払う分」にNを分割してN+1通り全探索．


def how_many_times_withdraw(withdraw, base, limit):
    result = 0
    while withdraw >= base:
        result += withdraw // (base ** limit)
        withdraw = withdraw % (base ** limit)
        limit -= 1
    return result + withdraw


def main():
    N = int(input())
    limit = []
    answer = float("inf")
    for yen in [6, 9]:
        i = 1
        while yen ** i <= N:
            i += 1
        limit.append(i - 1)
    for i in range(N + 1):
        answer = min(answer, how_many_times_withdraw(i, 6, limit[0]) + how_many_times_withdraw(N - i, 9, limit[1]))
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
from collections import Counter
#from scipy.misc import comb

N = int(input())

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

for i in range(1,N+1):
    c6 = 1
    while c6 <= i:
        ans[i] = min(ans[i], ans[i-c6]+1)
        c6 *= 6
    c9 = 1
    while c9 <= i:
        ans[i] = min(ans[i], ans[i-c9]+1)
        c9 *= 9

print(ans[N])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)


class memoRec():
    def __init__(self, n):
        self.max_n = 110000
        self.memo = [n] * self.max_n
        self.memo[0] = 0
        self.n = n

    def power6(self, s, i):
        self.memo[i] = min(self.memo[i], self.memo[i - s] + 1)
        if i - s * 6 < 0:
            return
        return self.power6(s * 6, i)

    def power9(self, s, i):
        self.memo[i] = min(self.memo[i], self.memo[i - s] + 1)
        if i - s * 9 < 0:
            return
        return self.power9(s * 9, i)

    def search(self, s):
        memo = self.power6(1, s)
        memo = self.power9(1, s)
        if s + 1 == self.n + 1:
            return
        return self.search(s + 1)


n = int(input())
mr = memoRec(n)
mr.search(1)
print(mr.memo[n])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)


def power6(n, memo, s):
    memo[n] = min(memo[n], memo[n - s] + 1)
    if n - s * 6 < 0:
        return memo
    return power6(n, memo, s * 6)


def power9(n, memo, s):
    memo[n] = min(memo[n], memo[n - s] + 1)
    if n - s * 9 < 0:
        return memo
    return power9(n, memo, s * 9)


def search(n, memo, s):
    memo = power6(s, memo, 1)
    memo = power9(s, memo, 1)
    if s + 1 == n + 1:
        return memo
    return search(n, memo, s + 1)


n = int(input())
max_n = 110000
dp = [n] * max_n

# 初期化
dp[0] = 0
memo = search(n, dp, 0)
print(memo[n])

Submission status: Accepted

Solution code:
# 貰うDP

n = int(input())


max_n = 110000
dp = [n] * max_n

# 初期化
dp[0] = 0

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

print(dp[n])

Submission status: Accepted

Solution code:
# 配るDP

n = int(input())


max_n = 110000
dp = [n] * max_n

# 初期化
dp[0] = 0

for i in range(n):
    pow6, pow9 = 1, 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])

Submission status: Accepted

Solution code:
import math
n = int(input())
#n = 127
inf = float('inf')

dp = [inf]*(n+100000)
dp[0]=0
#print(dp)
#print(len(dp))

def motome(target):
    tmp = []
    for i in range(10):
        if 9**i <= n:
            tmp.append(9**i)
        if 6**i <= n:
            tmp.append(6**i)
    #print(tmp) 
    #[1, 6, 36, 1, 9, 81]
    #print(dp)
    for k in range(target+1):
        for t in sorted(list(set(tmp))):
            if k-t>=0:
                dp[k] = min(dp[k],1 + dp[k-t])
                #dp[k] = min([dp[k-t] for t in tmp])
                '''
                try:
                    dp[k] = min(dp[k],1 + min([dp[k-t] for t in tmp]))
                except:
                    print(len(dp),dp[k-t],dp[k])
                    pass
                '''
        #print(k)
        #print([t for t in tmp])
        #print([dp[k-t] for t in tmp])

motome(n)
#print(dp[n-1])
print(dp[n])
#print(dp)
#print(dp[n+2])
#print(dp[n-1])
#print(dp[n])

Submission status: Accepted

Solution code:
n = int(input())
dp = [n]*(n+10)
dp[0] = 0
dp[1] = 1
for i in range(2, n+1):
    power = 1
    while power <= i:
        dp[i] = min(dp[i], 1 + dp[i-power])
        power *= 6
    power = 9
    while power <= i:
        dp[i] = min(dp[i], 1 + dp[i - power])
        power *= 9
print(dp[n])

Submission status: Accepted

Solution code:
def solve(n):
    cands = [6 ** i for i in range(1, 7)] + [9 ** i for i in range(1, 6)]
    m = len(cands)
    dp = [(0, 0)] * (n + 1)
    for i in range(6, n + 1):
        dp[i] = max(
            ((dp[i - cand][0] + cand, dp[i - cand][1] + 1) for cand in cands if i >= cand),
            key=lambda x: (x[0], -x[1])
        )
    return n - dp[n][0] + dp[n][1]

_n = int(input())
print(solve(_n))

Submission status: Accepted

Solution code:
n=int(input())
six=[6**i for i in range(1,7)]
nine=[9**i for i in range(1,6)]
credit=[1]
for i in six:
    credit.append(i)
for i in nine:
    credit.append(i)

credit.sort()

dp=[[float("inf") for _ in range(n+1)] for _ in range(len(credit))]
for i in range(n+1):
    dp[0][i]=i
for i in range(len(credit)):
    dp[i][0]=0
for c_i in range(1,len(credit)):
    for m_i in range(1,n+1):
        if credit[c_i]>m_i:
            dp[c_i][m_i]=dp[c_i-1][m_i]
            continue
        tmp=dp[c_i][m_i-credit[c_i]]+1
        dp[c_i][m_i]=min(tmp,dp[c_i-1][m_i])
#print(credit)
#import numpy as np
#print(np.array(dp))
print(dp[-1][-1])

Submission status: Accepted

Solution code:
N = int(input())

def num_withdraw_ll(N):
    dp = [N] * (N + 1)
    dp[0] = 0
    for n in range(0, N):
        dp[n + 1] = min(dp[n + 1], dp[n] + 1)
        coin = 6
        while n + coin <= N:
            dp[n + coin] = min(dp[n + coin], dp[n] + 1)
            coin *= 6
        coin = 9
        while n + coin <= N:
            dp[n + coin] = min(dp[n + coin], dp[n] + 1)
            coin *= 9
    return dp[N]

print(num_withdraw_ll(N))

Submission status: Accepted

Solution code:
N = int(input())

def num_withdraw_l(N):
    dp = [N] * (N + 1)
    dp[0] = 0
    for n in range(1, N+1):
        dp[n] = min(dp[n], dp[n - 1] + 1)
        coin = 6
        while coin <= N:
            dp[n] = min(dp[n], dp[n - coin] + 1)
            coin *= 6
        coin = 9
        while coin <= N:
            dp[n] = min(dp[n], dp[n - coin] + 1)
            coin *= 9
    return dp[N]

print(num_withdraw_l(N))

Submission status: Accepted

Solution code:
n = int(input())
ans = float('INF')
hand = []
tmp = 1
while tmp * 6 <= n:
    tmp *= 6
    hand.append(tmp)
tmp = 1
while tmp * 9 <= n:
    tmp *= 9
    hand.append(tmp)
 
hand.sort()
hand = hand[::-1]
dp = [i for i in range(n+1)]
for v in hand:
    for i in range(n+1-v):
        if dp[i] + 1 < dp[i+v]:
            dp[i+v] = dp[i] + 1
print(dp[n])

Submission status: Accepted

Solution code:
N = int(input())
dp = [0]*(N+1)
money = [1]
p = 1
while p <= N:
    p = p*6
    money.append(p)
p = 1
while p <= N:
    p = p*9
    money.append(p)
lenM = len(money)

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

print(dp[N])

Submission status: Accepted

Solution code:
a = int(input())
l = [6**i for i in range(10) if 6**i < 10**5]
l += [9**i for i in range(10) if 9**i < 10**5]
l = sorted(list(set(l)))

ans = [10 ** 9 for i in range(a+1)]
ans[0] = 0

for i in range(a):
  for j in l:
#    print(j)
    if i + j <= a:
      ans[i+j] = min(ans[i] + 1, ans[i+j])

print(ans[a])

Submission status: Accepted

Solution code:
n = int(input())

dp = [10 ** 6] * (n+1)

dp[0] = 0

for i in range(n+1):
    for j in range(n):
        if i + 6 ** j > n:
            break
        dp[i + 6 ** j] = min(dp[i + 6 ** j], dp[i] + 1)
        if not i + 9 ** j > n:
            dp[i + 9 ** j] = min(dp[i + 9 ** j], dp[i] + 1)

print(dp[n])

Submission status: Accepted

Solution code:
d = tuple([1] + [6**i for i in range(1, 7)] + [9**i for i in range(1, 6)])
M = 10**5+1
B = [float("inf")]*M
B[0] = 0
for i in range(M):
  for j in d:
    if i+j < M:
      B[i+j] = min(B[i+j], B[i]+1)
n = int(input())
print(B[n])

Submission status: Accepted

Solution code:
l = [1, 6, 9, 36, 81, 216, 729, 1296, 6561, 7776,46656, 59049]
n = int(input())
ans = [10**9 for _ in range(n+1)]
ans[0] = 0

for i in range(n):
    for j in l:
        if i + j <= n:
            ans[i+j] = min(ans[i] + 1,ans[i+j])
        
print(ans[n])

Submission status: Accepted

Solution code:
n = int(input())
MAX_N = 10**6
dp = [MAX_N] * MAX_N
dp[0] = 0

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N=input()
dp=[ float("inf") for _ in range(N+1) ]
dp[0]=0

#6円
for k in range(1,10**5):
    yen=6**k
    for i in range(N+1):
        if i+yen<=N:
            dp[i+yen]=min(dp[i+yen],dp[i]+1)
    if N<=yen:break

#9円
for k in range(1,10**5):
    yen=9**k
    for i in range(N+1):
        if i+yen<=N:
            dp[i+yen]=min(dp[i+yen],dp[i]+1)
    if N<=yen:break


#1円
for i in range(N+1):
    if i+1<=N:
        dp[i+1]=min(dp[i+1],dp[i]+1)


print dp[N]

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N=input()
dp=[ float("inf") for _ in range(N+1) ]
dp[0]=0

#9円
for k in range(1,10**5):
    yen=9**k
    for i in range(N+1):
        if i+yen<=N:
            dp[i+yen]=min(dp[i+yen],dp[i]+1)
    if N<=yen:break

#6円
for k in range(1,10**5):
    yen=6**k
    for i in range(N+1):
        if i+yen<=N:
            dp[i+yen]=min(dp[i+yen],dp[i]+1)
    if N<=yen:break

#1円
for i in range(N+1):
    if i+1<=N:
        dp[i+1]=min(dp[i+1],dp[i]+1)


print dp[N]

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N=input()
dp=[ float("inf") for _ in range(N+1) ]
dp[0]=0

#1円
for i in range(N+1):
    if i+1<=N:
        dp[i+1]=min(dp[i+1],dp[i]+1)
#6円
for k in range(1,10**5):
    yen=6**k
    for i in range(N+1):
        if i+yen<=N:
            dp[i+yen]=min(dp[i+yen],dp[i]+1)
    if N<=yen:break

#9円
for k in range(1,10**5):
    yen=9**k
    for i in range(N+1):
        if i+yen<=N:
            dp[i+yen]=min(dp[i+yen],dp[i]+1)
    if N<=yen:break

print dp[N]

Submission status: Accepted

Solution code:
N = int(input())

INF = float('inf')
dp = [INF] * (N+10)
dp[0] = 0

coin6 = [6**n for n in range(1,10) if 6**n <= N]
coin9 = [9**n for n in range(1,10) if 9**n <= N]

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

Submission status: Accepted

Solution code:
N = int(input())

INF = float('inf')
dp = [INF] * (N+10)
dp[0] = 0

coin6 = [6**n for n in range(1,10) if 6**n <= N]
coin9 = [9**n for n in range(1,10) if 9**n <= N]

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

Submission status: Accepted

Solution code:
# coding:utf-8

n = int(input().rstrip())

dic = [None for i in range(n + 1)]
def get_ans(amount:int):
    if dic[amount] is not None:
        return dic[amount]

    if amount <= 0:
        return 0

    ans = amount

    for i in reversed(range(6)):
        num = pow(9, i)
        if num > amount:
            continue
        ret = get_ans(amount - num) + 1
        ans = min(ans, ret)

    for i in reversed(range(7)):
        num = pow(6, i)
        if num > amount:
            continue
        ret = get_ans(amount - num) + 1
        ans = min(ans, ret)

    dic[amount] = ans
    return ans

print(get_ans(n))

Submission status: Accepted

Solution code:
import math

N = int(input())
NMAX = 100010
dp = [float('inf')] * NMAX
dp[0] = 0
for i in range(1, N + 1):
    dp[i] = i
    if i >= 6:
        for j in range(1, int(math.log(NMAX, 6)) + 1):
            dp[i] = min(dp[i], dp[i - 6 ** j] + 1)

    if i >= 9:
        for j in range(1, int(math.log(NMAX, 9)) + 1):
            dp[i] = min(dp[i], dp[i - 9 ** j] + 1)
# print(dp)
print(dp[N])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
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)