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())
minC = n
for i in range(n+1):
    cnt = 0
    t = i
    while t > 0:
        cnt += t%6
        t //= 6
    t = n-i
    
    while t > 0:
        cnt += t%9
        t //= 9
        
    if minC > cnt:
        minC = cnt
print(minC)

Submission status: Accepted

Solution code:
N = int(input())
list6 = [6**x for x in range(0,7) ]
list9 = [9**x for x in range(0,6) ]
result = {}

def f(x):
    if x < 6:
        return x
    elif x in result:
        return result[x] 
    else:
        max6 = max(y for y in list6 if y <= x)
        max9 = max(y for y in list9 if y <= x)
        x6 = x - max6
        x9 = x - max9
        result[x] = min(f(x6)+ 1,f(x9)+ 1)
        return result[x]

print(f(N))

Submission status: Accepted

Solution code:
n = int(input())

dp = [float('inf')]*100001
dp[0] = 0
for i in range(1,100001):
    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:
N = int(input())

sixs = [6**i for i in range(1,7)]
nines = [9**i for i in range(1,6)]
tmp = {}

def dfs(n):
  if(n < 6):
    return n

  if(n in tmp):
    return tmp[n]

  m = 10**9+7
  if(n >= 9):
    max_nine = max(nine for nine in nines if nine <= n)
    if(n%max_nine == 0):
      m = min(m, n // max_nine)
    else:
      m = min(m, dfs(n - max_nine) + 1)

  max_six = max(six for six in sixs if six <= n)
  if(n%max_six == 0):
    m = min(m, n // max_six)

  tmp[n] = min(m, dfs(n - max_six) + 1)
  return tmp[n]

print(dfs(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

print(res)

Submission status: Accepted

Solution code:
N = int(input())

six = [pow(6, i + 1) for i in range(10) if pow(6, i + 1) <= N]
nine = [pow(9, i + 1) for i in range(10) if pow(9, i + 1) <= N]

d = [1] + six + nine
d.sort()

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

dp = [[i + 1 if j == 0 else 0 for i in range(N)] for j in range(len(d))]

for i in range(1, len(d)):
  for j in range(N):
    if j + 1 == d[i]:
      dp[i][j] = 1  
    elif j < d[i]:
      dp[i][j] = dp[i - 1][j]
    else:
      dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - d[i]] + 1, dp[i][j - d[i]] + 1)

#for i in dp:
#  print(i)

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

Submission status: Accepted

Solution code:
n = int(input())
dp = [int(i) for i in range(10 ** 5 + 1)]

for i in [6,9]:
    v = i
    while v < 10 ** 5:
        for j in range(len(dp)):
            if j+v <= 10 ** 5:
                dp[j+v] =min(dp[j]+1,dp[j+v])
        v *= i      
        
print(dp[n])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
max_n = 10 ** 5

dp = [int(i) for i in range(max_n + 1)]

for i in (6,9):
    v = i
    while v < max_n:
        for j in range(len(dp)):
            if j + v < max_n+1:
                dp[j+v] = min(dp[j+v],dp[j]+1)
        v *= i
        
print(dp[n])

Submission status: Accepted

Solution code:
n = int(input())
dp = [0] * 100001
potential = [1]
k = 6
while(k < 100000):
    potential.append(k)
    k *= 6
k = 9
while(k < 100000):
    potential.append(k)
    k *= 9
for i in range(1,100001):
    pre = list(filter(lambda x: x<=i, potential))
    dp[i] = min(list(map(lambda x: dp[i-x], pre))) + 1
print(dp[n])

Submission status: Accepted

Solution code:
N = int(input())

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

Submission status: Accepted

Solution code:
memos = {}
nines = [9 ** n for n in range(1, 6)]
sixs = [6 ** n for n in range(1, 7)]


def solve(N):
    if N < 6:
        return N
    if N in memos:
        return memos[N]
    n = 10 ** 9
    if N >= 9:
        nine_max = max(n for n in nines if n <= N)
        if N % nine_max == 0:
            n = min(n, N // nine_max)
        else:
            n = min(n, solve(N - nine_max) + 1)

    six_max = max(n for n in sixs if n <= N)
    if N % six_max == 0:
        n = min(n, N // six_max)

    memos[N] = min(n, solve(N - six_max) + 1)
    return memos[N]

if __name__ == "__main__":
    N = int(input())
    print(solve(N))

Submission status: Accepted

Solution code:
n=int(input())

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

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

print(dp[n])

Submission status: Accepted

Solution code:
import sys
n = int(input())
if n<6:
  print(n)
  sys.exit()
ans = n%3
n -= n%3
nine = n//9
res = 10**10
for i in range(nine,-1,-1):
    r = n-9*i
    if r%6==0:
        num = 0
        while i>0:
            if i%9!=0:
                num+= i%9
                i -=i%9
            i = i//9
        s = r//6
        while s>0:
            if s%6!=0:
                num+= s%6
                s -=s%6
            s = s//6
        res = min(res,num)
print(ans+res)

Submission status: Accepted

Solution code:

dp = [float('inf')]*100010
dp[0] = 0
N = int(input())
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:
def main():
    N = int(input())
    dp = [N] * (N + 1)
    dp[0] = 0
    for n in range(1, N + 1):
        i = 1
        while n >= i:
            dp[n] = min(dp[n], dp[n - i] + 1)
            i *= 6
        j = 1
        while n >= j:
            dp[n] = min(dp[n], dp[n - j] + 1)
            j *= 9
    print(dp[N])


main()

Submission status: Accepted

Solution code:
N = int(input())
L = [1]
for i in range(N):
	if 6**(i+1) <=N:
		L.append(6**(i+1))
	if 9**(i+1) <= N:
		L.append(9**(i+1))
	if 6**(i+1) >N:
		break
L.sort(reverse =True)
dp = []
dp = [float("inf")]*(N+1)

dp[0] = 0

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

print(dp[N])

Submission status: Accepted

Solution code:
n = int(input())

from collections import deque
q = deque([0])
pre = {}
while True:
    mon = q.popleft()
    if mon == n:
        ans = 0
        while True:
            mon = pre[mon]
            ans += 1
            if mon == 0:
                break
        break
    six = 1
    while six <= n - mon:
        if six + mon not in pre:
            q.append(six + mon)
            pre[six + mon] = mon
        six *= 6
    nine = 9
    while nine <= n - mon:
        if nine + mon not in pre:
            q.append(nine + mon)
            pre[nine + mon] = mon
        nine *= 9

print(ans)

Submission status: Accepted

Solution code:
class DynamicProgramming(object):

    def __init__(self, item_n: int, border: int, obj_coef: list, sbj_coef: list, initializer: int = 0):
        self.item_n = item_n
        self.border = border
        self.table = [[initializer for _ in range(self.item_n + 1)] for _ in range(self.border + 1)]

        if len(obj_coef) == self.item_n:  # to 1-base
            obj_coef = [0] + obj_coef
        self.obj_coef = obj_coef

        if len(sbj_coef) == self.item_n:
            sbj_coef = [0] + sbj_coef
        self.sbj_coef = sbj_coef

    def __str__(self):
        return "\n".join(list(map(lambda l:
                                  " ".join(list(map(str, l)))
                                  , self.table)))

    def __repr__(self):
        return "DynamicProgramming object:\n" + \
               "item_n: " + str(self.item_n) + ", border: " + str(self.border) + "\n" +\
               "table:\n" + self.__str__()

    def solve(self, expr: callable) -> list:
        for weight_lim in range(1, self.border + 1):
            for item_idx in range(1, self.item_n + 1):
                self.table[weight_lim][item_idx] = expr(weight_lim, item_idx)

        return self.table

    def knapsack_expr(self, weight_lim: int, item_idx: int) -> int:
        res = self.table[weight_lim][item_idx - 1]
        if weight_lim - self.sbj_coef[item_idx] >= 0:
            res = max(res, self.table[weight_lim - self.sbj_coef[item_idx]][item_idx - 1] + self.obj_coef[item_idx])
        return res

    def coin_expr(self, target, coin_idx) -> int:
        if self.sbj_coef[coin_idx] == 1:
            res = target
        else:
            res = self.table[target][coin_idx - 1]
            if target - self.sbj_coef[coin_idx] >= 0:
                res = min(res, self.table[target - self.sbj_coef[coin_idx]][coin_idx] + self.obj_coef[coin_idx])
        return res

    def fill_0_idx_with(self, value: int) -> "DynamicProgramming":
        self.table[0] = [value for _ in range(self.item_n + 1)]
        for i in range(1, self.border + 1):
            self.table[i][0] = value
        return self


if __name__ == '__main__':
    N = int(input())
    values = sorted(list(set([6 ** i for i in range(7)] + [9 ** i for i in range(6)])))
    values_len = len(values)
    dp = DynamicProgramming(values_len, N, [1 for _ in range(values_len)], values, initializer=int(10e5))\
        .fill_0_idx_with(0)
    print(dp.solve(dp.coin_expr)[N][values_len])

Submission status: Accepted

Solution code:
N = int(input())


def f(x, base):
    ret = 0
    while x:
        x, m = divmod(x, base)
        ret += m
    return ret

print(min([f(i, 6) + f(N - i, 9) for i in range(N + 1)]))

Submission status: Accepted

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

for N1 in range(N+1):
    
    count = 0
    N2 = N - N1

    while N1 > 0:
        count += N1%6
        N1 = int(N1/6)
    
    while N2 > 0:
        count += N2%9
        N2 = int(N2/9)
    
    if ans > count:
        ans = count

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from copy import deepcopy

POSS = [1, 6, 36, 216, 1296, 7776, 46656, 9, 81, 729, 6561, 59049]
TMAX = 20
NMAX = 100000

def do_dp(n):
    dp = [i for i in range(NMAX + 1)]
    for t in range(TMAX):
        for i in reversed(range(NMAX + 1)):  # 配る
            for p in POSS:
                if i + p <= NMAX:
                    dp[i + p] = min(dp[i + p], dp[i] + 1)
    return dp[n]

def main():
    n = int(input())
    print(do_dp(n))

main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from copy import copy

POSS = [1, 6, 36, 216, 1296, 7776, 46656, 9, 81, 729, 6561, 59049]
TMAX = 20
NMAX = 100000

def do_dp(n):
    dp = [i for i in range(NMAX + 1)]
    for t in range(TMAX):
        pre = copy(dp)
        for i in range(NMAX + 1):  # 配る
            for p in POSS:
                if i + p <= NMAX:
                    dp[i + p] = min(dp[i + p], dp[i] + 1)
    return dp[n]

def main():
    n = int(input())
    print(do_dp(n))

main()

Submission status: Accepted

Solution code:

n = int(input())

ans = n

for i in range(n+1):
    cc = 0

    t = i
    while t>0:
        cc += t%6
        t //= 6

#    print('{},{}:'.format(i,cc),end = ' ')

    t = n-i
    while t>0:
        cc += t%9
        t //= 9
    
#   print('{},{}:'.format(n-i,cc))
    ans = min(ans, cc)

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
dp = [i for i in range(N+1)]
num = []
[num.append(6 ** i) for i in range(1, 7)]
[num.append(9 ** i) for i in range(1, 6)]
for i in range(N + 2):
    for add in num:
        if i + add > N: continue
        dp[i + add] = min(dp[i + add], dp[i] + 1)

print(dp[N])

Submission status: Accepted

Solution code:
import math
N = int(input())
def greed(N, a):
    if a == 6:
        L = [6**i for i in range(7, -1, -1)]
    else:
        L = [9**i for i in range(6, -1, -1)]
    num = 0
    while True:
        if N == 0:
            return num
        for l in L:
            if l <= N:
                N -= l
                break
        num += 1
A = []
for n in range(N+1):
    A.append(greed(n, 6) + greed(N-n, 9))
print(min(A))

Submission status: Accepted

Solution code:
def solve():
    n = int(input())
    dp = [0 for _ in range(n+1)] 

    for i in range(1, n+1):
        options = find_options(i)
        selected = min(map(lambda x: [x, dp[i - x]], options), key=lambda x: x[1])
        dp[i] = selected[1] + 1

    print(dp[n])

def find_options(n):
    sixs = find_sixs(n)
    nines = find_nines(n)
    options = [1]
    options.extend(sixs)
    options.extend(nines)
    return options


def find_sixs(n):
    sixs = 1
    powers = [] 
    count = 0
    while n > sixs:
        count += 1
        sixs *= 6
        powers.append(sixs)
    
    if sixs == n:
        return powers
    else:
        powers.pop()
    return powers

def find_nines(n):
    nines = 1
    powers = [] 
    count = 0
    while n > nines:
        count += 1
        nines *= 9
        powers.append(nines)
    
    if nines == n:
        return powers
    else:
        powers.pop()
    return powers

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
N = int(input())
six = []
i = 6
while i <= 100000:
    six.append(i)
    i *= 6
six.reverse()
nine = []
i = 9
while i <= 100000:
    nine.append(i)
    i *= 9
nine.reverse()
ansmin = 100000
for i in range(1+(N//6)):
    ans = 0
    money = N - 6 * i
    for j in nine:
        ans += money // j
        money = money % j
    ans += money
    money = 6 * i
    for j in six:
        ans += money // j
        money = money % j
    ansmin = min(ansmin, ans)
if ansmin == 100000:
    ansmin = N
print(ansmin)

Submission status: Accepted

Solution code:
n = int(input())
ans = 1000000

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

Submission status: Accepted

Solution code:
N = int(input())

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

for i in range(len(L)):
    for j in range(1,7):
        try: L[i + 6**j] = min(L[i + 6**j],L[i]+1)
        except: pass
    for j in range(1,6):
        try: L[i + 9**j] = min(L[i + 9**j],L[i]+1)
        except: pass
    try: L[i+1] = min(L[i+1],L[i]+1)
    except: pass
print(L[N])

Submission status: Accepted

Solution code:
n = int(input())

yen9=[9**i for i in range(6)]
yen6=[6**i for i in range(7)]
memo = {}

def withdraw_times(n):
  if n in memo:
    return memo[n]
  if n ==0:
    return 0

  maxmoney9 = 0
  maxmoney6 =0
  for i in range(6):
    if yen9[i] <= n:
      maxmoney9 = max(yen9[i],maxmoney9)
      
  for i in range(7):
    if yen6[i] <= n:
      maxmoney6 = max(yen6[i],maxmoney6)
      
  memo[n] =  min(withdraw_times(n-maxmoney6),withdraw_times(n-maxmoney9))+1
  return memo[n]

print(withdraw_times(n))

Submission status: Accepted

Solution code:
n = int(input())

ans = 10 ** 5

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

Submission status: Accepted

Solution code:
import math
N = int(input())

dp = [10**7 for i in range(100010)]
dp[0] = 0

for i in range(1,N+1):
    dp[i] = min(dp[i-1]+1,min([dp[i-pow(6,j)]+1 for j in range(int(math.log(i,6)+1))]),min([dp[i-pow(9,j)]+1 for j in range(int(math.log(i+10**(-10),9))+1)]))

print(dp[N])

Submission status: Accepted

Solution code:
six=[6**i for i in range(1,7)][::-1]
nine=[9**i for i in range(1,6)][::-1]
N=int(input())

ans=[]
def find(n,a):
    if n<6:
        ans.append(n+a)
        return
    for s in six:
        if s<=n:
            find(n-s,a+1)
            break
    for s in nine:
        if s<=n:
            find(n-s,a+1)
            break
find(N,0)
print(min(ans))

Submission status: Accepted

Solution code:
six=[6**i for i in range(1,7)][::-1]
nine=[9**i for i in range(1,6)][::-1]
N=int(input())

ans=[]
def find(n,a):
    if n<6: ans.append(n+a)
    for s in six:
        if s<=n:
            find(n-s,a+1)
            break
    for s in nine:
        if s<=n:
            find(n-s,a+1)
            break
find(N,0)
print(min(ans))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

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

    d_list = [1]
    k = 1
    while True:
        if 6 ** k <= N:
            d_list.append(6 ** k)
            k += 1
        else:
            break
    k = 1
    while True:
        if 9 ** k <= N:
            d_list.append(9 ** k)
            k += 1
        else:
            break

    d_list.sort()

    dp = []
    for d in d_list:
        if d == 1:
            for i in range(N + 1):
                dp.append(i)
        else:
            for i in range(d, N + 1):
                dp[i] = min(dp[i], dp[i - d] + 1)


    print(dp[N])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
m = N
for i in range(N+1):
    t=N-i
    count=0
    while i>0:
        count+=i%6
        i=i//6
    while t>0:
        count+=t%9
        t=t//9
    m=min(m,count)
print(m)

Submission status: Accepted

Solution code:
N = int(input())

dp = [int(i) for i in range(N+1)]
B6 = [6**i for i in range(1,7)]
B9 = [9**i for i in range(1,6)]
L = B6 + B9
L = sorted(list(set(L)))

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

Submission status: Accepted

Solution code:
N = int(input())

ans = 0
if N<6:
    ans = N
else:
    amari = N%3
    N = N-amari

    #準備として１度に引き出せる金額を列挙（N以下）
    hiki = []
    i=1
    #6の累乗
    while True:
        if 6**i<=N:
            hiki.append(6**i)
        else:
            break
        i+=1
    #9の累乗
    i=1
    while True:
        if 9**i<=N:
            hiki.append(9**i)
        else:
            break
        i+=1
    hiki.sort()

    #動的計画法でテーブルを作る
    #テーブルは
    #0円を引き出すのに必要な回数、3円を引き出すのに必要な回数、6円を引き出すのに必要な回数
    #9円を引き出すのに必要な回数、12円を引き出すのに必要な回数、15円を引き出すのに必要な回数・・・と続く
    table = [0,3]
    i=6
    while True:
        if i in hiki:
            table.append(1)
        else:
            tableTmp=[]
            for j in hiki:
                if i-j<0:
                    break
                else:
                    tableTmp.append(table[(i-j)//3]+1)
            table.append(min(tableTmp))
        if i == N:
            break
        i += 3
    ans = table[N//3] + amari

print(ans)

Submission status: Accepted

Solution code:
import copy
N=int(input())
six = [6**i for i in range(1,8)][::-1]
nine = [9**i for i in range(1,8)] [::-1]
def DP(n):
	if n < 6:
		return n
	tmp = n
	count6 = 0
	count9 = 0
	for sixx in six:
		if sixx <= n:
			n -= sixx
			count6 = 1
			break
	count6 += DP(n)
	n = tmp
	if n < 9:
		return count6
	for ninee in nine:
		if ninee<= n:
			n -= ninee
			count9 = 1
			break
	count9 += DP(n)
	n = tmp
	return min(count6,count9)
print(DP(N))

Submission status: Accepted

Solution code:
def inpl(): return list(map(int, input().split()))


def num(i, j):
    if i == 0:
        return 0
    
    

N = int(input())

ans = [N] * (N+1)
ans[0] = 0
ans[1] = 1
for i in range(2, N+1):
    ans[i] = min(ans[i], ans[i-1]+1)
    for num in [6, 9]:
        tmp = num
        while i - tmp >= 0:
            ans[i] = min(ans[i], ans[i-tmp] + 1, ans[i-1]+1)
            tmp *= num
print(ans[-1])

Submission status: Accepted

Solution code:
n = int(input())

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
s = [1]
a = 6
b = 9
while a <= N:
    s.append(a)
    a *= 6

while b<= N:
    s.append(b)
    b *= 9
s.sort()


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


for i in range(1,N+1):
    temp = []
    for j in s:
        if (i-j >= 0):
            if (dp[i-j] != -1):
                temp.append(dp[i-j]+1)
        else:
            break
    dp[i] = min(temp)

print(dp[N])

Submission status: Accepted

Solution code:
n = int(input())
A = []

for s in range(n + 1):
    count = 0
    t = n - s
    while s > 0:
        count += s % 6
        s //= 6
    while t > 0:
        count += t % 9
        t //= 9
    A.append(count)
    
print(min(A))

Submission status: Accepted

Solution code:
N=int(input())
A=[]
for i in range(1,10):
    if 6**i<=100000:
        A.append(6**i)
    if 9**i<=100000:
        A.append(9**i)
L=[i for i in range(100001)]
A.sort()

for i in range(len(A)):
    for j in range(1,100001):
        if j>=A[i]:
            L[j]=min(L[j],L[j-A[i]]+1)
print(L[N])

Submission status: Accepted

Solution code:

n = int(input())

ark = float("INF")
if n < 50000:
    for l in range(2):  # 59049
        abc = (n - (59049*l))
        if abc < 0:
            break
        for k in range(3):  # 46656
            abc = (n - (46656 * k+59049*l))
            if abc < 0:
                break
            for j in range(6):  # 7776
                abc = (n - (776 * j + 46656 * k+59049*l))
                if abc < 0:
                    break
                for h in range(4):  # 1296,6
                    abc = (n - (1296 * h+ 7776 * j + 46656 * k+59049*l))
                    if abc < 0:
                        break
                    for g in range(6):  # 729,9
                        abc = (n - (729 * g + 1296 * h+ 7776 * j + 46656 * k+59049*l))
                        if abc < 0:
                            break
                        for f in range(4):#216,5(4)
                            abc = (n - (216 * f+ 729 * g + 1296 * h+ 7776 * j + 46656 * k+59049*l))
                            if abc < 0:
                                break
                            for e in range(4):  # 81
                                abc = (n - (81 * e + 216 * f + 729 * g + 1296 * h+ 7776 * j + 46656 * k+59049*l))
                                if abc < 0:
                                    break
                                for d in range(5):  # 36
                                    abc = (n - (36 * d + 81 * e + 216 * f + 729 * g + 1296 * h+ 7776 * j + 46656 * k+59049*l))
                                    if abc < 0:
                                        break
                                    for c in range(4):  # 9
                                        abc = (n - (9 * c + 36 * d + 81 * e + 216 * f + 729 * g + 1296 * h + 7776 * j + 46656 * k+59049*l))
                                        if abc < 0:
                                            break
                                        for b in range(3):  # 6
                                            abc = (n - (6 * b + 9 * c + 36 * d + 81 * e + 216 * f + 729 * g + 1296 * h + 7776 * j + 46656 * k+59049*l))
                                            if abc < 0:
                                                break
                                            for a in range(6):  # 1
                                                abc = (n - (1*a+6*b+9*c+36*d+81*e+216*f+729*g+1296*h+7776*j+46656*k+59049*l))
                                                if abc < 0:
                                                    break
                                                if abc % 6561 == 0 and abc >= 0:
                                                    i = abc//6561
                                                    if ark > a+b+c+d+e+f+g+h+i+j+k+l:
                                                        ark = a+b+c+d+e+f+g+h+i+j+k+l
else:
    for l in range(2):  # 59049
        abc = (n - (59049*l))
        if abc < 0:
            break
        for k in range(3):  # 46656
            abc = (n - (46656 * k+59049*l))
            if abc < 0:
                break
            for j in range(6):  # 7776
                abc = (n - (776 * j + 46656 * k+59049*l))
                if abc < 0:
                    break
                for h in range(3):  # 1296,6
                    abc = (n - (1296 * h+ 7776 * j + 46656 * k+59049*l))
                    if abc < 0:
                        break
                    for g in range(4):  # 729,9
                        abc = (n - (729 * g + 1296 * h+ 7776 * j + 46656 * k+59049*l))
                        if abc < 0:
                            break
                        for f in range(3):#216,5(4)
                            abc = (n - (216 * f+ 729 * g + 1296 * h+ 7776 * j + 46656 * k+59049*l))
                            if abc < 0:
                                break
                            for e in range(4):  # 81
                                abc = (n - (81 * e + 216 * f + 729 * g + 1296 * h+ 7776 * j + 46656 * k+59049*l))
                                if abc < 0:
                                    break
                                for d in range(5):  # 36
                                    abc = (n - (36 * d + 81 * e + 216 * f + 729 * g + 1296 * h+ 7776 * j + 46656 * k+59049*l))
                                    if abc < 0:
                                        break
                                    for c in range(4):  # 9
                                        abc = (n - (9 * c + 36 * d + 81 * e + 216 * f + 729 * g + 1296 * h + 7776 * j + 46656 * k+59049*l))
                                        if abc < 0:
                                            break
                                        for b in range(3):  # 6
                                            abc = (n - (6 * b + 9 * c + 36 * d + 81 * e + 216 * f + 729 * g + 1296 * h + 7776 * j + 46656 * k+59049*l))
                                            if abc < 0:
                                                break
                                            for a in range(6):  # 1
                                                abc = (n - (1*a+6*b+9*c+36*d+81*e+216*f+729*g+1296*h+7776*j+46656*k+59049*l))
                                                if abc < 0:
                                                    break
                                                if abc % 6561 == 0 and abc >= 0:
                                                    i = abc//6561
                                                    if ark > a+b+c+d+e+f+g+h+i+j+k+l:
                                                        ark = a+b+c+d+e+f+g+h+i+j+k+l
print(ark)

Submission status: Accepted

Solution code:
N = int(input())
dp = [N + 1 for i in range(N+1)]
dp[0] = 0
for i in range(1,N+1):
    j = 0
    while i - pow(6,j) >= 0:
        if dp[i-pow(6,j)] + 1 < dp[i]:
            dp[i] = dp[i-pow(6,j)] + 1
        j += 1
    j = 0
    while i - pow(9,j) >= 0:
        if dp[i-pow(9,j)] + 1 < dp[i]:
            dp[i] = dp[i-pow(9,j)] + 1
        j += 1
print(dp[N])

Submission status: Accepted

Solution code:
n = int(input())
min = n
for i in range(n+1):
    tmp = i
    sum = 0
    while tmp>0:
        sum += tmp%6
        tmp = int(tmp/6)
    tmp = n-i
    while tmp>0:
        sum += tmp%9
        tmp = int(tmp/9)
    min = sum if min>sum else min
print(min)

Submission status: Accepted

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

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

print(dp[-1])

Submission status: Accepted

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

for i in range(n + 1):
    count = 0
    
    s = i
    while s > 0:
        count += s % 6
        s = s // 6
        
    t = n - i
    while t > 0:
        count += t % 9
        t = t // 9
        
    if ans > count:
        ans = count
        
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
res = n

for i in range(n+1):
    c = 0
    t = i
    while t>0:
        c += t%6
        t = int(t/6)

    t = n-i

    while t>0:
        c += t%9
        t = int(t/9)

    if res>c:
        res = c


print(res)

Submission status: Accepted

Solution code:
N = int(input())

Dp = [1000000]*(N+1)
Dp[0] = 0
for i in range(1,N+1):
    p = 0
    q = 0
    Dp[i] = Dp[i-1]+1
    while 6**p <= i:
        Dp[i] = min([Dp[i],Dp[i-6**p]+1])
        p += 1
    while 9**q <= i:
        Dp[i] = min([Dp[i],Dp[i-9**q]+1])
        q += 1
print(Dp[N])

Submission status: Accepted

Solution code:
# coding: utf-8

n = int(input())

#（↓）n円をおろすときの最小の出金回数をdp[n]に格納する。
#（↓）0円をおろすには0回の出金でよいのでdp[0]=0を初期値として設定する。
dp = [0]

#（↓）おろす金額がi円（=1,2,3,...,n）の場合を順番に考える。
for i in range(1,n+1):

    #（↓）i円を出金するときにありうる出金回数を全部Qに格納する。
    #（↓）全ての出金方法を検討した後で、Qの最小値、すなわちn円をおろすのに
    #（↓）必要な最小の出金回数をdp[i]に格納する。
    Q = []

    Q.append(1+dp[i-1])

    p6 = 1
    while i >= 6**p6:
        Q.append(1+dp[i-6**p6])
        p6 += 1

    p9 = 1
    while i >= 9**p9:
        Q.append(1+dp[i-9**p9])
        p9 += 1

    dp.append(min(Q))

print(dp[n])

Submission status: Accepted

Solution code:
def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]


MAX = 100000
N = int(input())

block = [1]
cnt = 6
while cnt <= MAX:
    block.append(cnt)
    cnt *= 6

cnt = 9
while cnt <= MAX:
    block.append(cnt)
    cnt *= 9

dp = [int(1e18)]*(MAX+1)
dp[0] = 0
for i in range(MAX):
    for e in block:
        if i + e <= MAX:
            dp[i+e] = min(dp[i+e], dp[i] + 1)

print(dp[N])

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    vs = [1]
    v = 6
    while v <= n:
        vs.append(v)
        v *= 6
    v = 9
    while v <= n:
        vs.append(v)
        v *= 9
    vs.sort()
    nums = [1 << 30] * (n + 1)
    nums[0] = 0
    for i in range(0, n):
        for v in vs:
            j = i + v
            if j > n:
                break
            nums[j] = min(nums[j], nums[i] + 1)
    print(nums[n])


if __name__ == '__main__':
    main()