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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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
#print(L)
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])
#print(dp)

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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()#[1,6,9,36,81]
dp = [float("Inf")]*(n+1)
dp[0] = 0
for i in range(n+1):#0~81
  for j in L:#1,6,9
    if i+j <= n:
      dp[i+j] = min(dp[i+j],dp[i]+1)#dp=[0,1,...1,.1]
    else:
      break
print(dp[n])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
# dp answer
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])

Submission status: Accepted

Solution code:
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
        # print(ans, j)

        # print(ans, j, N)
    ans = min(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
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
'''
# 配るDP
for i in range(N):
    pow6 = 1
    while i + pow6 <= N:
        dp[i + pow6] = min(dp[i + pow6], dp[i] + 1)
        pow6 *= 6

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

print(dp[N])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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()
# print(curr)

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

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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[:100])
print(dp[n])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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

#配列dp[N+1]にインデックスの数字を作るための最小手数をメモっていく
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)

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------


# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N = int(input())

# dp[i+100000] : i 円を引き出すのに必要な最小回数 
dp = [0]*(N+100010)
# dp[99999] までを大きな数で初期化しておく
for i in range(100000):
    dp[i] = 10**10

# dp[100000] : 0円を引き出すのに必要な最小回数 = 0 で初期化済み
# dp[100001] : 1円を引き出すのに必要な最小回数 から処理していく
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])

Submission status: Accepted

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


n=int(input())

#dpで解く再帰

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

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

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

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

N = ir()
answer = N
# 6円で払う部分と9円で払う部分を分ける
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)

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

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

# def create_money(i):
#     money = []
#     tmp = 1
#     for _ in range(math.floor(math.log(N, i))):
#         tmp *= i
#         money.append(tmp)
    
#     return money

# money = [1]
# money += create_money(6)
# money += create_money(9)

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

Submission status: Accepted

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

# def create_money(i):
#     money = []
#     tmp = 1
#     for _ in range(math.floor(math.log(N, i))):
#         tmp *= i
#         money.append(tmp)
    
#     return money

# money = [1]
# money += create_money(6)
# money += create_money(9)

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

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

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

# dp
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)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *

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

for i in range(2, N+1):
	L = [6**x for x in range(int(log2(i)/log2(6))+1)] + [9**x for x in range(1, int(log2(i)/log2(9))+1)]
	dp[i] = min([dp[i-y] for y in L]) + 1

print(dp[N])

Submission status: Accepted

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

INF = 10**8

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

    memo[x] = res
    return res

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

Submission status: Accepted

Solution code:
n = int(input())
dp = [200000] * (n+10)
dp[0] = 0
for i in range(1,n+1):
    dp[i] = min(dp[i-1]+1, dp[i])
    
    six = 6
    while i - six >= 0:
        dp[i] = min(dp[i-six]+1, dp[i])
        six *= 6 

    nine = 9
    while i - nine >= 0:
        dp[i] = min(dp[i-nine]+1, dp[i])
        nine *= 9

print(dp[n])

Submission status: Accepted

Solution code:
n = int(input())
dp = [200000] * (n+10)
dp[0] = 0
# dp[1] = 1
for i in range(n):
    dp[i+1] = min(dp[i+1], dp[i]+1)
    six = 6
    while i + six <= n:
        dp[i+six] = min(dp[i+six], dp[i]+1)
        six *= 6 

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

print(dp[n])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
pow6s = [6, 36, 216, 1296, 7776, 46656]
pow9s = [9, 81, 729, 6561, 59049]
coins = sorted([1] + pow6s + pow9s)
dp = [n+1] * (n+1)
dp[0] = 0
dp[1] = 1
for i in range(len(coins)):
    c = coins[i]
    ndp = dp[:]
    for j in range(n+1):
        if j-c >= 0:
            ndp[j] = min(dp[j], ndp[j-c] + 1)
    dp = ndp
print(dp[-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
n = int(input())
pow6s = [6, 36, 216, 1296, 7776, 46656]
pow9s = [9, 81, 729, 6561, 59049]
dp = [-1] * (n+1)
def dfs(n):
    if n == 0:
        return 0
    if dp[n] != -1:
        return dp[n]
    mincount = n + 1
    for p6 in pow6s:
        if n-p6 >= 0:
            mincount = min(mincount, dfs(n-p6) + 1)
    for p9 in pow9s:
        if n-p9 >= 0:
            mincount = min(mincount, dfs(n-p9) + 1)
    
    dp[n] = min(mincount, dfs(n-1) + 1)
    return dp[n]

print(dfs(n))