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:
import bisect as bi

li6 = [6 ** i for i in range(7)]
li9 = [9 ** i for i in range(6)]

def s69(n):
    if n < 6:
        return n
    else:
        s6 = li6[bi.bisect(li6, n) - 1]
        s9 = li9[bi.bisect(li9, n) - 1]
        return min(n // s6 + s69(n % s6), 1 + s69(n - s9))


print(s69(int(input())))

Submission status: Accepted

Solution code:
#abc099-c
n=int(input())

#dp配列と引き出した金額を対応させる
dp=[float('inf')]*(n+1)
dp[0]=0
l=[1,6,9]
for i in range(n+1):

    for j in range(3):
        num=1
        deposit=l[j]
        while i+deposit<=n:
            if deposit==1:
                dp[i+1]=min(dp[i+1],dp[i]+1)
                break
            dp[deposit+i]=min(dp[deposit+i],dp[i]+1)
            num+=1
            # 次にとる金額を決める
            deposit=l[j]**num
print(dp[-1])

Submission status: Accepted

Solution code:
n = int(input())

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

for i in range(1,4):
    for j in range(n+1):
        if i == 1:
            if j > 0:
                dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]+1, dp[i][j-1]+1)
        elif i == 2:
            for k in range(1,10):
                if j - 6**k >= 0:
                    dp[i][j] = min(dp[i][j],dp[i-1][j], dp[i-1][j-6**k]+1, dp[i][j-6**k]+1)
                else:
                    dp[i][j] = min(dp[i-1][j],dp[i][j])
        else:
            for k in range(1,10):
                if j - 9**k >= 0:
                    dp[i][j] = min(dp[i][j],dp[i-1][j], dp[i-1][j-9**k]+1, dp[i][j-9**k]+1)
                else:
                    dp[i][j] = min(dp[i-1][j], dp[i][j])

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

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

MAX_N = 110000

N = iin()

dp = [-1 for _ in range(MAX_N)]
dp[0] = 0

que = collections.deque()

que.append(0)

while (len(que) != 0):
    v = que.popleft()
    pow6 = 1
    while v+pow6 <= N:
        if dp[v+pow6] == -1:
            dp[v+pow6] = dp[v] + 1
            que.append(v+ pow6)
        pow6 *= 6
    pow9 = 1
    while v+pow9 <= N:
        if dp[v+pow9] == -1:
            dp[v+pow9] = dp[v] + 1
            que.append(v+pow9)
        pow9 *= 9
print(dp[N])

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

MAX_N = 110000

N = iin()

dp = [10**10 for _ in range(MAX_N)]
dp[0] = 0

for i in range(0, 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:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

MAX_N = 110000

N = iin()

dp = [10**10 for _ in range(MAX_N)]
dp[0] = 0

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
print(dp[N])

Submission status: Accepted

Solution code:
n = int(input())
l = [1]
a = 6
b = 9
while True:
    if a > 100000:
        break
    else:
        l.append(a)
        l.append(b)
        a *= 6
        b *= 9

dp = [[10000000]*(n+1) for i in range(len(l)+1)]
dp[0][0] = 0
for i in range(len(l)):
    for j in range(n+1):
        if j < l[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j],dp[i+1][j-l[i]]+1)
print(dp[len(l)][n])

Submission status: Accepted

Solution code:
def knapsack(N,W,weight,value):
  #初期化
  dp=[[10**7 for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1):
    dp[0][i]=i
  #DP
  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
        dp[i+1][w]=min(dp[i+1][w-weight[i]]+value[i], dp[i][w])
      else:
        dp[i+1][w]=dp[i][w]
        
  
  return dp[N][W]

N = 12
W = int(input())
weight = [1,6,36,216,1296,7776,46656,9,81,729,6561,59049]
value = [1,1,1,1,1,1,1,1,1,1,1,1,1]

a = knapsack(N,W,weight,value)

print(a)

Submission status: Accepted

Solution code:
N = int(input())
 
h = [1]
 
t = []
i = 1
while True:
  t.append(6**i)
  i += 1
  if t[-1]>10000:
    break
h.extend(t)
 
t = []
i = 1
while True:
  t.append(9**i)
  i += 1
  if t[-1]>10000:
    break
h.extend(t)
 
h.sort()
 
DP = []
DP.append(0)
 
hlen = len(h)
for i in range(1,N+1):
  m = 999999
  for j in range(hlen):
    if i-h[j]<0:
      break
    else:
      if m>DP[i-h[j]] + 1:
        m = DP[i-h[j]] + 1
  DP.append(m)  
print(DP[N])

Submission status: Accepted

Solution code:
N = int(input())

h = [1]

t = []
i = 1
while True:
  t.append(6**i)
  i += 1
  if t[-1]>10000:
    break
h.extend(t)

t = []
i = 1
while True:
  t.append(9**i)
  i += 1
  if t[-1]>10000:
    break
h.extend(t)

h.sort()

DP = []
DP.append((0, 0))

hlen = len(h)
for i in range(1,N+1):
  m = 999999
  p = 0
  for j in range(hlen):
    if i-h[j]<0:
      break
    else:
      if m>DP[i-h[j]][0] + 1:
        m = DP[i-h[j]][0] + 1
        p = h[j] + DP[i-h[j]][0]
  DP.append((m, p))  
print(DP[N][0])

Submission status: Accepted

Solution code:
N = int(input())
done = []
#探索スタート地点を「探索候補スタック」に積む
arr = [N]
ans = 0
stop = 0
  
#while スタックが空っぽになるまで
while arr:
  a = arr.pop(0)
  
  if a == -1:
    ans += 1
  
  done.append(a)
  Next = []
  if a-1 >= 0:
    Next.append(a-1)

  if a-46656 >= 0:
    Next.append(a-46656)
  elif a-7776 >= 0:
    Next.append(a-7776)
  elif a-1296 >= 0:
    Next.append(a-1296)
  elif a-216 >= 0:
    Next.append(a-216)
  elif a-36 >= 0:
    Next.append(a-36)
  elif a-6 >= 0:
    Next.append(a-6)

  if a-59049 >= 0:
    Next.append(a-59049)
  elif a-6561 >= 0:
    Next.append(a-6561)
  elif a-729 >= 0:
    Next.append(a-729)
  elif a-81 >= 0:
    Next.append(a-81)
  elif a-9 >= 0:
    Next.append(a-9)
    
  if -1 not in arr:
    arr.append(-1)   

  while Next:
    i = Next.pop(0)
    if i in done:
      continue
    elif i in arr:
      continue
    else:
      arr.append(i)
      if i == 0:
        stop = 1
        break
  if stop == 1:
    break

print(ans+1)

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
done = deque()
#探索スタート地点を「探索候補スタック」に積む
arr =  deque([N])
ans = 0
stop = 0
  
#while スタックが空っぽになるまで
while arr:
  a = arr.popleft()
  
  if a == -1:
    ans += 1
  
  done.append(a)
  Next = deque()
  if a-1 >= 0:
    Next.append(a-1)

  if a-46656 >= 0:
    Next.append(a-46656)
  elif a-7776 >= 0:
    Next.append(a-7776)
  elif a-1296 >= 0:
    Next.append(a-1296)
  elif a-216 >= 0:
    Next.append(a-216)
  elif a-36 >= 0:
    Next.append(a-36)
  elif a-6 >= 0:
    Next.append(a-6)

  if a-59049 >= 0:
    Next.append(a-59049)
  elif a-6561 >= 0:
    Next.append(a-6561)
  elif a-729 >= 0:
    Next.append(a-729)
  elif a-81 >= 0:
    Next.append(a-81)
  elif a-9 >= 0:
    Next.append(a-9)
    
  if -1 not in arr:
    arr.append(-1)
    

  while Next:
    i = Next.pop()
    if i in done:
      continue
    elif i in arr:
      continue
    else:
      arr.append(i)
      if i == 0:
        stop = 1
        break
  if stop == 1:
    break

print(ans+1)

Submission status: Accepted

Solution code:
from functools import lru_cache

@lru_cache(maxsize=1000000)
def fx(n):
  if n == 0:
    return 0
  if n == 1:
    return 1
  arr = []
  cnt = 0
  
  if n < 6:
    b = fx(n-1)+1
    arr.append(b)
  while n-6**cnt >= 0:
    cnt += 1
  if cnt > 1:
    
    x = n-(6**(cnt-1))
    b = fx(x)+1
    arr.append(b)

  cnt = 0
  while n-9**cnt >= 0:
    cnt += 1
  if cnt > 1:
    x = n-(9**(cnt-1))
    b = fx(x)+1
    arr.append(b)
  
  return min(arr)
  
N = int(input())
print(fx(N))

Submission status: Accepted

Solution code:
from functools import lru_cache

@lru_cache(maxsize=1000)
def fx(n):
  if n == 0:
    return 0
  if n == 1:
    return 1
  arr = []
  cnt = 0
  
  if n < 6:
    b = fx(n-1)+1
    arr.append(b)
  while n-6**cnt >= 0:
    cnt += 1
  if cnt > 1:
    
    x = n-(6**(cnt-1))
    b = fx(x)+1
    arr.append(b)

  cnt = 0
  while n-9**cnt >= 0:
    cnt += 1
  if cnt > 1:
    x = n-(9**(cnt-1))
    b = fx(x)+1
    arr.append(b)
  
  return min(arr)
  
N = int(input())
print(fx(N))

Submission status: Accepted

Solution code:
# from math import log
n = int(input())


# def make_list(n, x):
#     return [x ** i for i in range(1, int(log(n, x))+1)]
nums = [1]
# N = int(input())
for i in range(20):
    if 100000 >= 6**i:
        nums.append(6**i)
    if 100000 >= 9**i:
        nums.append(9**i)

# sixes = make_list(n, 6)
# nines = make_list(n, 9)
# nums = [1] + sixes + nines

dp = [float('inf')] * (n+1)
for num in nums:
    for i in range(1, n+1):  # 1~nまでのn円について調べる
        if i == num:
            dp[i] = 1
        elif i > num:
            dp[i] = min(dp[i], dp[i-num]+1)
print(dp[n])

Submission status: Accepted

Solution code:
from math import log
n = int(input())


# def make_list(n, x):
#     return [x ** i for i in range(1, int(log(n, x))+1)]
#
#
# sixes = make_list(n, 6)
# nines = make_list(n, 9)
# nums = [1] + sixes + nines

nums = [1]
i = 1
num = 1
while num <= n:
    num = 6 ** i
    nums.append(num)
    i += 1
i = 1
num = 1
while num <= n:
    num = 9 ** i
    nums.append(num)
    i += 1


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

Submission status: Accepted

Solution code:
from math import log
n = int(input())


# def make_list(n, x):
#     return [x ** i for i in range(1, int(log(n, x))+1)]
#
#
# sixes = make_list(n, 6)
# nines = make_list(n, 9)
# nums = [1] + sixes + nines

nums = [1]
i = 1
num = 1
while num <= n:
    num = 6 ** i
    nums.append(num)
    i += 1
i = 1
num = 1
while num <= n:
    num = 9 ** i
    nums.append(num)
    i += 1


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

Submission status: Accepted

Solution code:
bank = [1]
N = int(input())
for i in range(20):
    if 100000 >= 6**i:
        bank.append(6**i)
    if 100000 >= 9**i:
        bank.append(9**i)
# print(bank)
dp = [[10**10]*(N+1) for _ in range(len(bank)+1)]

dp[0][0] = 0
# i番目の引き出し方法を使う
for i in range(len(bank)):
    for j in range(N+1):
        # 使わない場合
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        # 使う場合
        if j + bank[i] > N:  # Nを超えるならcontinue
            continue
        dp[i+1][j+bank[i]] = min(dp[i][j]+1, dp[i+1][j]+1)
print(dp[len(bank)][N])

Submission status: Accepted

Solution code:
wt = int(input())
w = [1]
for i in range(7):
    w.append(6 ** (i + 1))
for i in range(5):
    w.append(9 ** (i + 1))
n = len(w)
dp = [[float("inf") for i in range(wt + 1)] for j in range(n + 1)]
dp[0][0] = 0
for i in range(n):
    for j in range(wt + 1):
        if j >= w[i]:
            dp[i + 1][j] = min(dp[i + 1][j - w[i]] + 1, dp[i][j])
        else:
            dp[i + 1][j] = dp[i][j]
print(dp[n][wt])

Submission status: Accepted

Solution code:
n = int(input())

l9 = [9**(i+1) for i in range(6)]
l6 = [6**(i+1) for i in range(6)]
l9.sort(reverse=True)
l6.sort(reverse=True)
ans = n
for i in range(n):
    n9 = i+1
    n6 = n-n9
    tmp = 0

    while (n9 >= 9):
        for t in l9:
            if t <= n9:
                n9 -= t
                tmp += 1
                break
    n6 += n9
    while (n6 >= 6):
        for t in l6:
            if t <= n6:
                n6 -= t
                tmp += 1
                break
    ans = min(ans, tmp+n6)
print(ans)

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

# MOD = 998244353


N = int(sys.stdin.buffer.readline())

s = {0}
ans = 0
while True:
    ns = set()
    for n in s:
        d = 0
        while n + 6 ** d <= N:
            ns.add(n + 6 ** d)
            d += 1
        d = 0
        while n + 9 ** d <= N:
            ns.add(n + 9 ** d)
            d += 1
    ans += 1
    if N in ns:
        break
    s = ns
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

ans = 10**5
for a in range(0, N+1):
	cnt = 0
	t = 1
	for i in range(7):
		cnt += (a//t)%6
		t *= 6
	t = 1
	for i in range(6):
		cnt += ((N-a)//t)%9
		t *= 9
	ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
can=set()

can.add(1)
i=1
ans=0
while True:
  ans=6**i
  if ans<=100000:
    can.add(ans)
    i+=1
  else:
    break
    
j=1
ans=0
while True:
  ans=9**j
  if ans<=100000:
    can.add(ans)
    j+=1
  else:
    break

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

for k in range(2,N+1):
  mini=10000000
  for item in can:
    if k-item>=0:
      mini=min(mini, dp[k-item]+1)
  dp[k]=mini

print(dp[-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools

class cin():
    def int():
        return int(sys.stdin.readline().rstrip())
    def string():
        return sys.stdin.readline().rstrip()
    def mapInt():
        return [int(x) for x in cin.string().split()]
    def stringList(n):
        return [input() for i in range(n)]

class Util():
    def round_up(a,b):
        return -(-a // b)
    def toUpperMultiple(a,x):
        return Util.round_up(a,x) * x
    def toLowerMultiple(a,x):
        return (a // x) * x

N = cin.int()
dp = [0] * (N + 1)
dp[0] = 0
for i in range(1,N + 1):
    dp[i] = i
    p = 1
    while p <= i:
        dp[i] = min(dp[i],dp[i - p] + 1)
        p *= 6
    p = 1
    while p <= i:
        dp[i] = min(dp[i],dp[i - p] + 1)
        p *= 9
print(dp[N])

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  
  l=[1]
  for i in range(1,20):
    a=6**i
    if a<=n:
      l.append(a)
    b=9**i
    if b<=n:
      l.append(b)

  l.sort()

  dp=[inf for _ in range(n+1)]
  dp[0]=0

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

  return dp[n]

# main()
print(main())

Submission status: Accepted

Solution code:
N = int(input())

prices = [1]
idx = 1
while 6 ** idx <= N:
    prices.append(6 ** idx)
    idx += 1
idx = 1
while 9 ** idx <= N:
    prices.append(9 ** idx)
    idx += 1

prices.sort()

dp = [float('inf') for _ in range(N + 1)]
dp[0] = 0
for n in range(N + 1):
    for price in prices:
        dp[n] = min(dp[n], dp[n - price] + 1)

print(dp[-1])

Submission status: Accepted

Solution code:
N = int(input())
dp = [float('inf') for i in range(N+1)]
dp[0] = 0
if N >= 6:
    dp[6] = 1
def below_power(n,a):
    "n以下になるa**xのxの最大値を求める"
    x = 0
    while n >= a**x:
        x += 1
    return x-1
nine = below_power(N,9)
six = below_power(N,6)
for i in range(six,0,-1):
    for j in range(N+1):
        if j - 6**i >= 0:
            dp[j] = min(dp[j],dp[j-6**i]+1)
        if j - 9**i >= 0:
            dp[j] = min(dp[j],dp[j-9**i]+1)       
ans = dp[N]
for i in range(1,min(N+1,6)):
    ans = min(ans,dp[N-i]+i)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
dp = [float('inf') for i in range(N+1)]
dp[0] = 0
if N >= 6:
    dp[6] = 1
def below_power(n,a):
    "n以下になるa**xのxの最大値を求める"
    x = 0
    while n >= a**x:
        x += 1
    return x-1
nine = below_power(N,9)
six = below_power(N,6)
for i in range(six,0,-1):
    for j in range(N+1):
        if j - 6**i >= 0:
            dp[j] = min(dp[j],dp[j-6**i]+1)
for i in range(nine,0,-1):
    for j in range(N+1):
        if j - 9**i >= 0:
            dp[j] = min(dp[j],dp[j-9**i]+1)       
ans = dp[N]
for i in range(1,min(N+1,6)):
    ans = min(ans,dp[N-i]+i)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
import itertools
A=list(itertools.product([0,1,2,3,4,5],repeat=6))
ans=10**6
cnt=0
for i in A:
  a=6*i[0]+36*i[1]+216*i[2]+1296*i[3]+7776*i[4]+46656*i[5]
  if a<=N:
    b=N-a
    cnt=sum(i)
    for j in range(6,0,-1):
      d=b//(9**j)
      b-=(9**j)*d
      cnt+=d
    cnt+=b
    ans=min(cnt,ans)
print(ans)

Submission status: Accepted

Solution code:
import math
n=int(input())
ans=n
for i in range(n+1):
    cnt=0
    t=i #入力nをtとjに分けて考える(6の累乗分と9の累乗分への分割)
    while t>0:
        cnt+=t%6 #tを6で割ったあまり(=1円として引き出す分)
        t//=6 #tを6で割ったときの商に置き換える
    j=n-i
    while j>0: #9の場合も同じようにやる
        cnt+=j%9
        j//=9
    ans=min(ans,cnt)
    #n回1円で引き出すのと、6または9の累乗円を使って引き出すのとどっちが回数少ないか
print(ans)

Submission status: Accepted

Solution code:
import math

def chmin(a, b):
    if a > b:
        a = b
        return a
    else:
        return a

n = int(input())

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

p = int(math.log(n, 6))
q = int(math.log(n, 9))

for i in range(1, n + 1):
    dp[i] = chmin(dp[i], dp[i - 1] + 1)
    for j in range(1, p + 2):
        if i - 6 ** j >= 0:
            dp[i] = chmin(dp[i], dp[i - 6 ** j] + 1)
        else:
            break
    for k in range(1, q + 2):
        if i - 9 ** k >= 0:
            dp[i] = chmin(dp[i], dp[i - 9 ** k] + 1)
        else:
            break

print(dp[n])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
N = int(input())
memo = [-1]*(N+1)
def rec(n):
    if n == 0:
        return 0
    if memo[n] != -1:
        return memo[n]
    res = n
    m = 1
    while m <= n:
        res = min(res,rec(n-m)+1)
        m *= 6
    m = 1
    while m <= n:
        res = min(res,rec(n-m)+1)
        m *= 9
    memo[n] = res
    return memo[n]

print(rec(N))

Submission status: Accepted

Solution code:
def main():
    N = int(input())

    dp = [999999999999 for _ in range(N + 1)]
    dp[0] = 0

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

        # 6 yen
        i = 6
        while i <= n:
            dp[n] = min(dp[n], dp[n - i] + 1)
            i *= 6

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

    print(dp[N])


main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    N = int(input())

    dp = [0] * (10 ** 5 + 1)
    dp[1] = 1

    x = [1]
    x.extend([6 ** x for x in range(1, 8)])
    x.extend([9 ** x for x in range(1, 6)])


    for i in range(2, 10 ** 5 + 1):
        tmp = []
        for v in x:
            if i >= v:
                tmp.append(dp[i - v] + 1)

        dp[i] = min(tmp)

    print(dp[N])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools

N = int(input())

nine_list = [9**i for i in range(0, 6)]
six_list = [6**i for i in range(1, 7)]

ans = float("inf")
for combi in itertools.product([i for i in range(6)], repeat=6):
    # print(combi)
    count = sum(combi)
    six_sum = sum([a*b for a, b in zip(six_list, combi)])
    if N < six_sum:
        continue
    rest = N - six_sum
    for nine in reversed(nine_list):
        if nine > rest:
            continue
        count += rest // nine
        rest = rest % nine
    ans = min(ans, count)

print(ans)

Submission status: Accepted

Solution code:
from math import log

def n_number(num:int , n:int)->list:
    #n進数に直す
    ans = []
    while num > 0:
        ans.append(num%n)
        num = num // n
    return ans[::-1]


def main():
    N = int(input())
    ans = N
    for six in range(N + 1):
        ans = min(ans,sum(n_number(six,6)) + sum(n_number(N - six,9)))
    print(ans)
    return
        
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())

INF = 10**9

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

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

Submission status: Accepted

Solution code:
def f(num, base):
    # calc max Pth Power
    ret = 1
    while ret <= num:
        ret *= base
    return ret // base


def main():
    N = {int(input())}
    ans = 0
    while (all(N)):
        N = {x - f(x, 6) for x in N} | {x - f(x, 9) for x in N}
        ans += 1
    print(ans)
    return


main()

Submission status: Accepted

Solution code:
def f(num, base):
    # calc max Pth Power
    ret = 1
    while ret <= num:
        ret *= base
    return ret // base


def main():
    N = int(input())
    st = {N}
    ans = 0
    while (all(st)):
        st = {x - f(x, 6) for x in st} | {x - f(x, 9) for x in st}
        ans += 1
    print(ans)
    return


main()

Submission status: Accepted

Solution code:
n = int(input())
a = [1]

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

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

dp = [0] * 100001
for i in range(1, n+1):
    m = dp[i-1] + 1
    for v in a:
        if i - v < 0:
            continue
        if m > dp[i-v] + 1:
            m = dp[i-v] + 1
    dp[i] = m

print(dp[n])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import product, permutations, combinations
N=int(input())
dp = [N for i in range(N+1)]
dp[0] = 0
for i in range(1, N+1):
    power = 1
    while power <= i:
        dp[i] = min(dp[i], dp[i-power] + 1)
        power *= 6
    power = 1
    while power <= i:
        dp[i] = min(dp[i], dp[i-power] + 1)
        power *= 9
print(dp[N])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
memo = [-1]*(N+1)
import sys
sys.setrecursionlimit(10**8)
def rec(n):
    if n == 0:return 0
    if memo[n] != -1:return memo[n]

    res = float('inf')

    pow6 = 1
    while pow6 <= n:
        res = min(res,rec(n-pow6)+1)
        pow6 *= 6

    pow9 = 1
    while pow9 <= n:
        res = min(res,rec(n-pow9)+1)
        pow9 *= 9

    memo[n] = res
    return memo[n]

print(rec(N))

Submission status: Accepted

Solution code:
"""
import bisect
N = int(input())
ans = 0
hikidashi_list = [1, 6, 9]
tmp_6 = 6
tmp_9 = 9
while tmp_6 < N:
    tmp_6 *= 6
    hikidashi_list.append(tmp_6)

while tmp_9 < N:
    tmp_9 *= 9
    hikidashi_list.append(tmp_9)

hikidashi_list.sort()
while N > 0:
    now = bisect.bisect_left(hikidashi_list, N)
    if now == 0:
        N -= 1
    else:
        N -= hikidashi_list[now-1]
    ans += 1
print(ans)

# 貪欲に大きいお金から取るのでは無理
# N = 13 解3 (6, 6, 1)  本法5 (9, 1, 1, 1, 1)
"""

# DP
N = int(input())
dp = [100000000] * (N+1)
dp[0] = 0
dp[1] = 1
ans = 0
hikidashi_list = [1, 6, 9]
tmp_6 = 6
tmp_9 = 9
while tmp_6 < N:
    tmp_6 *= 6
    hikidashi_list.append(tmp_6)

while tmp_9 < N:
    tmp_9 *= 9
    hikidashi_list.append(tmp_9)
hikidashi_list.sort()
for i in range(N+1):
    for k in hikidashi_list:
        if i + k > N :
            break
        dp[i+k] = min(dp[i] + 1, dp[i+k])

print(dp[N])

Submission status: Accepted

Solution code:
# 配る DP
N = int(input())

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

# 配る DP --- dp[n] から遷移を出して行く
for i in range(N):
  pow6 = 1
  while pow6+i <= N:
    dp[i+pow6] = min(dp[i]+1, dp[i+pow6])
    pow6 *= 6
    
  pow9 = 1
  while pow9+i <= N:
    dp[i+pow9] = min(dp[i]+1, dp[i+pow9])
    pow9 *= 9

print(dp[N])

Submission status: Accepted

Solution code:
# ボトムアップ 貰う DP
N = int(input())

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

# 貰う DP --- dp[n] に遷移を集める
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

print(dp[N])

Submission status: Accepted

Solution code:
n = int(input())

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

pow6 = []
i = 1
while 6**i <= 10**5:
    pow6.append(6**i)
    i += 1
pow9 = []
i = 1
while 9**i <= 10**5:
    pow9.append(9**i)
    i += 1
money = [1] + pow6 + pow9

for i in range(n):
    for k in money:
        if n >= i+k >= 0:
            dp[i+k] = min(dp[i+k], dp[i] + 1)

print(dp[-1])

Submission status: Accepted

Solution code:
N = int(input())
dp = [0]

for i in range(1, N + 1):
	cur = min(1 + dp[i - 1], 10 ** 10)
	
	j = 1
	while i - 6 ** j >= 0:
		cur = min(1 + dp[i - 6 ** j], cur)
		j += 1
	
	j = 1
	while i - 9 ** j >= 0:
		cur = min(1 + dp[i - 9 ** j], cur)
		j += 1
		
	dp.append(cur)
	
print(dp[-1])

Submission status: Accepted

Solution code:
N = int(input())
lis = []
six = 6
nine = 9
while six<=100000:
    lis.append(six)
    six *= 6
while nine<=100000:
    lis.append(nine)
    nine *= 9
lis.sort()
dp = [0]
for i in range(1,N+1):
    tmp = dp[i-1]+1
    for l in lis:
        if i-l<0:
            break
        tmp = min(tmp,dp[i-l]+1)
    dp.append(tmp)
print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())
lis = []
six = 6
nine = 9
while six<=100000:
    lis.append(six)
    six *= 6
while nine<=100000:
    lis.append(nine)
    nine *= 9
lis.sort()
dp = [0]
for i in range(1,N+1):
    tmp = dp[i-1]+1
    for l in lis:
        if i-l<0:
            break
        tmp = min(tmp,dp[i-l]+1)
    dp.append(tmp)
print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())

pattern = [1, 6, 36, 216, 1296, 7776, 46656, 9, 81, 729, 6561, 59049]

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

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

print(dp[N])

Submission status: Accepted

Solution code:

n = int(input())
dp = [10**9]*(n+1)
L = [6**i for i in range(1,7)]
L += [9**i for i in range(1,6)]

dp[0] = 0

for i in range(1,n+1):
    dp[i] = dp[i-1]+1
    k = 6
    while i-k >=0:
        dp[i] = min(dp[i],dp[i-k]+1)
        k *=6
    k = 9
    while i-k >=0:
        dp[i] = min(dp[i],dp[i-k]+1)
        k *=9
    #print(dp)
print(dp[n])