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())
money_list=[1,6,36,216,1296,7776,46656,9,81,729,6561,59049]
dp=[0]
for i in range(1,N+1):
    dp.append(100000)

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

Submission status: Accepted

Solution code:
N=int(input())
money_list=[1,6,36,216,1296,7776,46656,9,81,729,6561,59049]
dp=[0]
for i in range(1,N+1):
    dp.append(100000)

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

Submission status: Accepted

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

A.append(1)
for i in range(1,7):
    A.append(6**i)
for i in range(1,6):
    A.append(9**i)
    
    
A.sort()
dp = [10*5+5]*(N+1)
dp[0] = 0
for i in range(1, N+1):
    for s in range(len(A)):
        if i-A[s] >= 0:
            dp[i] = min(dp[i-A[s]]+1, dp[i])
            
            
print(dp[N])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# AtCoder Beginner Contest
# Problem C


if __name__ == '__main__':
    n = int(input())
    dp = [0] + [100001 for _ in range(n + 1)]

    # See:
    # https://www.youtube.com/watch?v=I-8BnRkq6Ow
    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())
INF = 2*10**10
dp = [INF for x 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())
dp = [0] * (N + 1)
for i in range(1, N+1):
    dp[i] = float('inf')
    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:
import sys
N = int(input())
dp = [ 100000 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
    while power <= i:
        dp[i] = min(dp[i],dp[i-power]+1)
        power += 1
print(dp[N])

Submission status: Accepted

Solution code:
n = int(input())
a = [0] * (n+1)
for i in range(1,n+1):
    b = a[i-1] + 1
    c = 1
    d = 1
    while c <= i / 6:
        c *= 6
        b =  min(a[i-c]+1,b)
    while d <= i / 9:
        d *= 9
        b =  min(a[i-d]+1,b)
    a[i] = b
print(a[n])

Submission status: Accepted

Solution code:
n = int(input())

a = [0 for i in range(n+5)]

for i in range(1,n+2):
    b = a[i-1]+1
    c = 1
    d = 1
    while c*6 <= i:
        c *= 6
        b = min(a[i-c]+1,b)
    while d*9 <= i:
        d *= 9
        b = min(a[i-d]+1,b)
    a[i] = b
print(a[n])

Submission status: Accepted

Solution code:
n = int(input())

result = []
for i in range(n + 1):
    count = 0
    a, b = i , n - i
    while a > 0:
        count += a % 6
        a //= 6
    while b > 0:
        count += b % 9
        b //= 9
    result.append(count)
print(min(result))

Submission status: Accepted

Solution code:
import sys

#a, b = map(int, input().split(" "))
N = int(input())

arr = [0 for idx in range(100001)]

for i in range(1,10):
	if i >= 9:
		arr[i] = 1
	elif i >= 6:
		arr[i] = i - 5
	else:
		arr[i] = i;

six_mul = 6**2
nine_mul = 9**2
six_index = 6
nine_index = 9

for i in range(10, 100001):
	if i == six_mul:
		six_mul *= 6
		six_index *= 6
		arr[i] = 1
	elif i == nine_mul:
		nine_mul *= 9
		nine_index *= 9
		arr[i] = 1
	else:
		arr[i] = min(arr[i-1], min(arr[i-six_index], arr[i-nine_index]))+1
print(arr[N])

Submission status: Accepted

Solution code:
import math
N = int(input())
 
def Nsinpou(x, base):
    #配列を返す Nsin[0]が上位桁
    if x == 0: return [0]
    Nsin = []
    for i in range((round(math.log(x,base))+1)):
        ithdigit = x%(base**(i+1)) // (base ** i)
        Nsin.append(ithdigit)
    Nsin.reverse()
    return Nsin
 
ans = N
for i in range(N+1):
    coins = sum(Nsinpou(i,6)) + sum(Nsinpou(N-i,9))
    if coins < ans:
        ans = coins
    
print(ans)

Submission status: Accepted

Solution code:
def dfs(n):
    if n < 6:
        return n
    elif n < 9:
        return 1 + dfs(n - 6)
    
    six_max = 1
    nine_max = 1
    while six_max * 6 <= n:
        six_max *= 6
    
    while nine_max * 9 <= n:
        nine_max *= 9
    
    return min(dfs(n - nine_max), dfs(n - six_max)) + 1

print(dfs(int(input())))

Submission status: Accepted

Solution code:
import math
N = int(input())
 
def Nsinpou(x, base):
    #配列を返す Nsin[0]が上位桁 ex. 56(base=6) => [1,3,2]
    if x == 0: return [0] #log_n(0)の回避
    Nsin = []
    for i in range((int(round(math.log(x,base))//1)+1)):
        ithdigit = x%(base**(i+1)) // (base ** i)
        Nsin.append(ithdigit)
    Nsin.reverse()
    return Nsin
 
ans = N #最大でも1円玉N枚
for i in range(N+1): #分け方全探索
    coins = sum(Nsinpou(i,6)) + sum(Nsinpou(N-i,9))
    if coins < ans:
        ans = coins
    
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
dp=[float("inf")]*100010
dp[0]=0

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

print(dp[n])

Submission status: Accepted

Solution code:
#-*-coding:utf-8-*-

def main(): 
    N = int(input()) 
    num_list = set([1]) 
    i = 1 
    j = 1 
    while 6 ** i <= N: 
        num_list.add(6 ** i) 
        i += 1 
    while 9 ** j <= N: 
        num_list.add(9 ** j)
        j += 1 
    num_list = list(num_list) 
    num_list.sort()

    dp = [] 

    for i in range(1, N+1): 
        if i in num_list: 
            dp.append(1) 
        else: 
            temp = [] 
            for k in num_list: 
                if i - k > 0: 
                    temp.append(i - k) 
            small_dp = [dp[x-1] for x in temp] 
            dp.append(min(small_dp) + 1) 

    print(dp[-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def m():
    n = int(input())
    a = set()
    for i in range(100):
        tmp = 9 ** i
        if tmp > 100000:
            break
        a.add(tmp)
    for i in range(100):
        tmp = 6 ** i
        if tmp > 100000:
            break
        a.add(tmp)
    l = list(a)
    l.sort()
    dp = [0] * (n+1)
    dp[0] = 0
    for i in range(1,n+1):
        b = []
        for j in l:
            if j > i:
                break
            b.append(1 + dp[i-j])
        dp[i] = min(b)
    return dp[n]

print(m())

Submission status: Accepted

Solution code:
n=int(input())

m=n//3
r=n%3
a=[0]
for i in range(1,m+1):
	t=a[i-1]+3
	j=2
	while i>=j:
		t=min(t,a[i-j]+1)
		j*=6
	k=3
	while i>=k:
		t=min(t,a[i-k]+1)
		k*=9
	a.append(t)
print(a[m]+r)

Submission status: Accepted

Solution code:
N=int(input())
c=1,6,9,36,81,216,729,1296,6561,7776,46656,59049

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

Submission status: Accepted

Solution code:
l=[100000 for i in range(100001)]
l[0]=0
dif=[1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
for i in range(1,100001):
	for j in dif:
		if j>i:
			break
		l[i]=min(l[i],l[i-j]+1)
n=int(input())
print(l[n])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

N = int(input())

# ちょっと自分でいじった版

dp = [0] * (N+1)

for n in range(1, N+1):
    dp[n] = float("inf")
    power = 1
    while power <= n:
        dp[n] = min(dp[n], dp[n-power] + 1)
        power *= 6
    power = 1
    while power <= n:
        dp[n] = min(dp[n], dp[n-power] + 1)
        power *= 9

print(dp[N])

Submission status: Accepted

Solution code:
def times(money, mod):
  ans = 0
  while(money != 0):
    ans +=  money % mod
    money = money // mod
  return ans
 
c = []
n = int(input())
for i in range(n+1):
  c.append(times(i,6)+times(n-i,9))
print(min(c))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

N = int(input())

# 解説動画通りにDPしてみる

dp = [0] * 100001
# dp[0] = 0

for n in range(1, 100001):
    dp[n] = float("inf")
    power = 1
    while power <= n:
        dp[n] = min(dp[n], dp[n-power] + 1)
        power *= 6
    power = 1
    while power <= n:
        dp[n] = min(dp[n], dp[n-power] + 1)
        power *= 9

print(dp[N])

Submission status: Accepted

Solution code:
from bisect import bisect_right
N = int(input())
c = 0
def croku(N):
    roku =[0,1] + [6**i for i in range(1,7)]
    c = 0
    while N != 0:
        N = N - roku[bisect_right(roku,N)-1]
        c += 1
    return c

def ckyu(N):
    kyu = [0,1] + [9**i for i in range(1,6)]
    c = 0
    while N != 0:
        N = N - kyu[bisect_right(kyu,N)-1]
        c += 1
    return c

K = 10**5
for i in range(0,N+1):
    K = min(K, croku(i) + ckyu(N-i))
print(K)

Submission status: Accepted

Solution code:
N = int(input())

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

memo = [0 for i in range(N + 1)]

for i in range(N + 1):
    if i < a[0]:
        memo[i] = i
    elif i < a[1]:
        memo[i] = min(memo[i - 1], memo[i - a[0]]) + 1
    elif i < a[2]:
        memo[i] = min(memo[i - 1], memo[i - a[0]], memo[i - a[1]]) + 1
    elif i < a[3]:
        memo[i] = min(memo[i - 1], memo[i - a[0]], memo[i - a[1]],
                      memo[i - a[2]]) + 1
    elif i < a[4]:
        memo[i] = min(memo[i - 1], memo[i - a[0]], memo[i - a[1]],
                      memo[i - a[2]], memo[i - a[3]]) + 1
    elif i < a[5]:
        memo[i] = min(memo[i - 1], memo[i - a[0]], memo[i - a[1]],
                      memo[i - a[2]], memo[i - a[3]], memo[i - a[4]]) + 1
    elif i < a[6]:
        memo[i] = min(memo[i - 1], memo[i - a[0]], memo[i - a[1]],
                      memo[i - a[2]], memo[i - a[3]], memo[i - a[4]],
                      memo[i - a[5]]) + 1
    elif i < a[7]:
        memo[i] = min(memo[i - 1], memo[i - a[0]], memo[i - a[1]],
                      memo[i - a[2]], memo[i - a[3]], memo[i - a[4]],
                      memo[i - a[5]], memo[i - a[6]]) + 1
    elif i < a[8]:
        memo[i] = min(memo[i - 1], memo[i - a[0]], memo[i - a[1]],
                      memo[i - a[2]], memo[i - a[3]], memo[i - a[4]],
                      memo[i - a[5]], memo[i - a[6]], memo[i - a[7]]) + 1
    elif i < a[9]:
        memo[i] = min(memo[i - 1], memo[i - a[0]], memo[i - a[1]],
                      memo[i - a[2]], memo[i - a[3]], memo[i - a[4]],
                      memo[i - a[5]], memo[i - a[6]], memo[i - a[7]],
                      memo[i - a[8]]) + 1
    elif i < a[10]:
        memo[i] = min(memo[i - 1], memo[i - a[0]], memo[i - a[1]],
                      memo[i - a[2]], memo[i - a[3]], memo[i - a[4]],
                      memo[i - a[5]], memo[i - a[6]], memo[i - a[7]],
                      memo[i - a[8]], memo[i - a[9]]) + 1
    else:
        memo[i] = min(memo[i - 1], memo[i - a[0]], memo[i - a[1]],
                      memo[i - a[2]], memo[i - a[3]], memo[i - a[4]],
                      memo[i - a[5]], memo[i - a[6]], memo[i - a[7]],
                      memo[i - a[8]], memo[i - a[9]], memo[i - a[10]]) + 1

print(memo[N])

Submission status: Accepted

Solution code:
N = int(input())
def cn(X, n):
    if (int(X/n)):
        return cn(int(X/n), n)+str(X%n)
    return str(X%n)
def su(n):
  ans = 0
  for chara in n:
    ans += int(chara)
  return ans
lis = []
i = 0
while i <= N:
  lis.append(su(cn(i,6))+su(cn(N-i,9)))
  i += 1
print(min(lis))

Submission status: Accepted

Solution code:
N = int(input())
unit_list = [1, 6, 6**2, 6**3, 6**4, 6**5, 6**6, 9, 9**2, 9**3, 9**4, 9**5]
unit_list.sort(reverse=True)

memo = {}

def count_withdraw_Z(amount):
    result = []
    
    tmp = memo.get(amount, 0)
    if tmp != 0:
        return tmp
    
    for unit in unit_list:
        if unit == amount:
            memo[amount] = 1
            return 1
        elif unit < amount:
            result.append(count_withdraw_Z(amount - unit) + 1)
    
    memo[amount] = min(result)
    return memo[amount]

print(count_withdraw_Z(N))

Submission status: Accepted

Solution code:
N = int(input())
ans = N
for i in range(N + 1):
	count = 0
	temp = i
	while temp > 0:
		count += int(temp % 9)
		temp = int(temp / 9)
	temp = N - i
	while temp > 0:
		count += int(temp % 6)
		temp = int(temp / 6)
	if count < ans:
		ans = count
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
input_num = int(input())

combinations = [(pow1, pow2, pow3, pow4, pow5, pow6)
                for pow1 in range(0, 6)
                for pow2 in range(0, 6)
                for pow3 in range(0, 6)
                for pow4 in range(0, 6)
                for pow5 in range(0, 6)
                for pow6 in range(0, 6)]

num_withdraw_list = []
for combination in combinations:
    pow1, pow2, pow3, pow4, pow5, pow6 = combination
    withdraw6 = 6 ** 1 * pow1 + 6 ** 2 * pow2 + \
                6 ** 3 * pow3 + 6 ** 4 * pow4 + \
                6 ** 5 * pow5 + 6 ** 6 * pow6

    if withdraw6 > input_num:
        continue
    else:
        rest = input_num - withdraw6
        num_withdraw = sum(combination)
        for i in reversed(range(1, 6)):
            withdraw_i = rest // 9 ** i
            rest -= 9 ** i * withdraw_i
            num_withdraw += withdraw_i
        num_withdraw += rest
        num_withdraw_list.append(num_withdraw)

print(str(min(num_withdraw_list)))

Submission status: Accepted

Solution code:
def times(money, mod):
  ans = 0
  while(money != 0):
    ans +=  money % mod
    money = money // mod
  return ans

c = []
n = int(input())
for i in range(n+1):
  c.append(times(i,6)+times(n-i,9))
print(min(c))

Submission status: Accepted

Solution code:
n = int(raw_input())
item_9 = [59049, 6561, 729, 81, 9]
item_6 = [46656, 7776, 1296, 216, 36, 6]

def min_n(yen):
  if yen <= 5:
    return yen
  else:
    small_6 = small_9 = yen
    for x in item_9:
      if x > yen:
        continue
      else:
        small_9 = min_n(yen-x) + 1
        break
    for x in item_6:
      if x > yen:
        continue
      else:
        small_6 = min_n(yen-x) + 1
        break
  return min(small_9, small_6)

print(min_n(n))

Submission status: Accepted

Solution code:
import bisect
n = int(input())
s6 = [pow(6,i) for i in range(1,20)]
s9 = [pow(9,i) for i in range(1,20)]
cost = [-1]*(max(n+1,12))
for x in range(12):
  if x < 6:
    cost[x] = x
  elif x < 9:
    cost[x] = (x//6) + (x%6)
  else:
    cost[x] = (x//9) + (x%9)
    
def get_cost(x):
  if 0 <= cost[x]:
    return cost[x]
  div6 = bisect.bisect_right(s6,x)-1
  a = pow(10,18)
  b = pow(10,18)
  for i in range(1,(x//s6[div6])+1):
    tmp = get_cost(x - i*s6[div6])
    if i + tmp < a:
      a = i + tmp
  div9 = bisect.bisect_right(s9,x)-1
  for j in range(1,(x//s9[div9])+1):
    tmp = get_cost(x - j*s9[div9])
    if j + tmp < b:
      b = j + tmp
  cost[x] = min(a,b)
  return cost[x]
print(get_cost(n))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
numlist=[1, 6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049]
timeslis2=[0,]*(100001)
timeslis2[1]=1
numlist2=numlist[::-1]
def times2(N):
    if N!=0:
        if timeslis2[N]==0:
            mini2=[]
            i=0
            while i<=11 and len(mini2)<=2:
                if N-numlist2[i]>=0:
                    mini2.append(times2(N-numlist2[i]))
                #print(mini2,numlist2[i],i)
                i+=1
            mini2.sort()
            timeslis2[N]=mini2[0]+1
            return mini2[0]+1
        else:
            return timeslis2[N]
    return 0
print(times2(N))

Submission status: Accepted

Solution code:
memo = {}
def f(n):
    if n in memo:
        return memo[n]
    if n < 6:
        memo[n] = n
        return n
    ret = n
    for i in range(6, 0, -1):
        if 6 ** i <= n:
            t = f(n - 6 ** i) + 1
            if t < ret:
                ret = t

    for i in range(5, 0, -1):
        if 9 ** i <= n:
            t = f(n - 9 ** i) + 1
            if t < ret:
                ret = t

    memo[n] = ret
    return ret
def main():
    print(f(int(input())))

main()

Submission status: Accepted

Solution code:
n = int(input())

arr6 = []
for i in range(10):
	arr6.append(6**i)

arr9 = []
for i in range(10):
	arr9.append(9**i)


ans = float("inf")
for i in range(n+1):
	count = 0
	tmp = i
	while tmp > 0:
		t = 0
		while arr6[t] <= tmp:
			t+=1

		tmp -= arr6[t-1]
		count += 1

	tmp = n-i
	while tmp > 0:
		t = 0
		while arr9[t] <= tmp:
			t += 1
		tmp -= arr9[t-1]
		count += 1

	ans = min(ans,count)

print ans

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    N = int(input()) #引き出したい金額

    res = N #全部1円で引き出したときの回数
    for A in range(N+1):
        temp = 0
        tot = A
        while tot > 0:
            temp += tot % 6
            tot = tot // 6

        tot = N - A
        while tot > 0:
            temp += tot % 9
            tot = tot // 9
        if(res > temp):
            res = temp

    print(res)

Submission status: Accepted

Solution code:
N=int(input())
dp = [1000001] * (N+1)
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[N])

Submission status: Accepted

Solution code:
N=int(input())
dp=[0]*(N+1)
def f(n):
    p=0
    q=0
    m=n
    while n>=1:
        n//=9
        p+=1
    while m>=1:
        m//=6
        q+=1
    s=[]
    for i in range(p):
        s.append(9**i)
    for j in range(q):    
        s.append(6**j)
    s.pop(0)    
    return s
for i in range(1,N+1):
    dp[i]=dp[i-1]+1
    for j in f(i):
        dp[i]=min(dp[i-j]+1,dp[i])
print(dp[N])

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    n = int(input())

    min_count = n
    for i in range(0, n + 1):
        count = 0

        # pay i yen by 6^p
        t = i
        while t > 0:
            count += t % 6
            t //= 6

        t = n - i
        # pay n - i yen by 9^p
        while t > 0:
            count += t % 9
            t //= 9

        if count < min_count:
            min_count = count

    print(min_count)

Submission status: Accepted

Solution code:
N = int(input())
arr = sorted([6**x for x in range(1, 9) if 6**x <= N] + [9**x for x in range(1, 9) if 9**x <= N])
dp = [i for i in range(0,N+1)]
for i in range(2, N+1):
    dp[i] = 1+dp[i-1]
    for c in arr:
        if i - c >= 0:
            dp[i] = min([dp[i], 1+dp[i-c]])
print(dp[-1])

Submission status: Accepted

Solution code:
dp = [float("inf") for _ in range(100000 + 1)]
dp[0] = 0

N = int(input())

for i in range(len(dp)):
    if i == N:
        print(dp[i])
        break

    dp[i + 1] = min(dp[i + 1], dp[i] + 1)

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

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

Submission status: Accepted

Solution code:
n=int(input())
s=[i for i in range(n+1)]
a=[1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
for i in range(n+1):
    s[i]=i
for i in range(1,12):
    if a[i]<=n :
        k=a[i]
        for j in range(k,n+1):
            if s[j]>s[j-k]+1:
                s[j]=s[j-k]+1
print(s[n])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
i=1
x=[1]
while(6**i<=n):
    x.append(6**i)
    i+=1
i=1
while(9**i<=n):
    x.append(9**i)
    i+=1

dp=[0]
for i in range(1,n+1):
    k=n
    for j in x:
        if j<=i:
            k=min(dp[i-j]+1, k)
    dp.append(k)
print(dp[-1])

Submission status: Accepted

Solution code:
import math

n = int(input())

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

for i in range(1,n+1):
    tmp = float('inf')
    tmp6, tmp9 = 1,1
    while tmp6 <= i:
        if dp[i-tmp6]+1 < tmp:
            tmp = dp[i-tmp6] + 1
        tmp6 *= 6
    while tmp9 <= i:
        if dp[i-tmp9] + 1 < tmp:
            tmp = dp[i-tmp9] + 1
        tmp9 *= 9
    dp[i] = tmp

'''
    for j in range(int(math.log(i,6))+1):
        if dp[i-6**j]+1 < tmp:
            tmp = dp[i-6**j] + 1
    for j in range(int(math.log(i,9))+1):
        if dp[i-9**j]+1 < tmp:
            tmp = dp[i-9**j]+1
'''
    #dp[i] = tmp

print(dp[n])

Submission status: Accepted

Solution code:
n=int(input())
s=[]
t=1000
p=0
def f9(n,p):
    while n>=9:
        n//=9
        p+=1
        f9(n,p)
    return p
def f6(n,p):
    while n>=6:
        n//=6
        p+=1
        f6(n,p)
    return p    
s.append((n,0))
while s:
    a=s[0][0]
    b=s[0][1]
    if a<6:
        t=min(t,b+a)
    if t>=b+1:
        p=0
        s.append((a-9**f9(a,p),b+1))
        p=0
        s.append((a-6**f6(a,p),b+1))
    s.pop(0)    
print(t)

Submission status: Accepted

Solution code:
n = int(input())
l = [1]
for i in [6,9]:
    j = i
    while j <= n:
        l.append(j)
        j *= i

dp = [0]

for i in range(1,n+1):
    m = n
    for j in l:
        if j <= i:
            m = min(m,dp[i-j]+1)
    dp.append(m)
print(dp[-1])

Submission status: Accepted

Solution code:
n = int(input())
dp = [0 for i in range(n)]
a = [1]
i = 1
_ = 6
while _ <= n:
    a.append(_)
    i += 1
    _ = 6 ** i
i = 1
_ = 9
while _ <= n:
    a.append(_)
    i += 1
    _ = 9 ** i
len_a = len(a)
for i in range(n):
    target = []
    for j in range(len_a):
        if i + 1 >= a[j]:
            target.append(dp[i - a[j]])
    dp[i] = min(target) + 1
print(dp[n-1])

Submission status: Accepted

Solution code:
n=int(input())
ans=n
for i in range(n+1):
    c=0
    t=i
    while(t>0):
        c+=t%6
        t//=6
    t=n-i
    while(t>0):
        c+=t%9
        t//=9
    if(ans>c):ans=c
print(ans)

Submission status: Accepted

Solution code:
from itertools import count, takewhile, dropwhile
 
def dfs(n, max9, max6, d={0:0}):
    if n in d: 
      return d[n]
  
    max9 = next(dropwhile(lambda x: x>n, (max9 / 9**i for i in count())))
    max6 = next(dropwhile(lambda x: x>n, (max6 / 6**i for i in count())))
    d[n] = min(dfs(n-max9, max9, max6), dfs(n-max6, max9, max6)) + 1
    return d[n]
 
n = int(input())
 
max9 = max(takewhile(lambda x: x<=n, (9**i for i in count())))
max6 = max(takewhile(lambda x: x<=n, (6**i for i in count())))
 
print(dfs(n, max9, max6))

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n = ni()

dp = [99999999] * (n + 1)
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[n])

Submission status: Accepted

Solution code:
N = int(input())
vals = [1]

tmp = 6
while tmp <= 100000:
  vals.append(tmp)
  tmp *= 6

tmp = 9
while tmp <= 100000:
  vals.append(tmp)
  tmp *= 9

vals.sort()

dp = [0] + [float('inf')] * N
for n in range(1, N+1):
  i = 0
  while i < len(vals) and vals[i] <= n:
    dp[n] = min(dp[n], dp[n-vals[i]]+1)
    i += 1

print(dp[N])

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
 t = N-i
 while t>0:
  cc += t%9
  t //= 9
 if ans>cc:
  ans = cc

print("{}".format(ans))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
INF = 10**6

dp = [INF] * (N + 100)
dp[0] = 0

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

    power = 6
    while n - power >= 0:
        dp[n] = min(1 + dp[n - power], dp[n])
        power *= 6

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

print(dp[N])

Submission status: Accepted

Solution code:
N=int(input())

def num_6(A):
	i=0
	while True:
		if 6**i>A:
			return i-1
		i=i+1

def num_9(A):
	i=0
	while True:
		if 9**i>A:
			return i-1
		i=i+1

num_arr=[]
for i in range(N+1):
	num_6_max=num_6(i)
	num_9_max=num_9(N-i)
	a6_num=[]
	a9_num=[]
	A=i
	B=N-(i)
	for j in range(num_6_max+1):
		a6_num.append(A//(6**(num_6_max-j)))
		A=A-(6**(num_6_max-j))*a6_num[j]
	for j in range(num_9_max+1):
		a9_num.append(B//(9**(num_9_max-j)))
		B=B-(9**(num_9_max-j))*a9_num[j]
	num_arr.append(sum(a6_num)+sum(a9_num))
print(min(num_arr))

Submission status: Accepted

Solution code:
N = int(input())

pow_list = [pow(6, x) for x in range(0, 7)]
for i in range(0, 6):
    pow_list.append(pow(9, i))

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

for pow in pow_list:
    for i in range(pow, N + 1):
        dp[i] = min(dp[i], dp[i - pow] + 1)

print(dp[-1])

Submission status: Accepted

Solution code:
def main():
    """
    1 <= N <= 10^5
    """
    N = int(input())

    ans = rec(N)
    print(ans)


def test_ans():
    N_ans = [
        (127, 4),
        (3, 3),
        (44852, 16),
    ]
    for N, ans in N_ans:
        assert rec(N) == ans


def rec(N):
    import sys
    sys.setrecursionlimit(10 ** 7)
    memo = [-1] * (N+1)

    def _rec(i):
        if i == 0:
            return 0
        if memo[i] != -1:
            return memo[i]

        ans = N
        p = 1
        while p <= i:
            #print(6, i, i-p)
            ans = min(ans, _rec(i-p) + 1)
            p *= 6
        p = 1
        while p <= i:
            #print(9, i, i-p)
            ans = min(ans, _rec(i-p) + 1)
            p *= 9

        memo[i] = ans

        return ans

    ans = _rec(N)
    return ans


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

dp = [0]

for i in range(1, n+1):
    dp.append(100000)
    power = 1
    while (i - power >= 0):
        dp[i] = min(dp[i], 1 + dp[i - power])
        power *= 6

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

print(dp[n])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
six = [6 ** x for x in range(1, 10) if 6 ** x <= 100000]
nine = [9 ** x for x in range(1, 10) if 9 ** x <= 100000]
sn = set(six + nine)

dp = [0] + [x for x in range(1, n + 1)]
for i in sn:
    for j in range(i, n + 1):
        dp[j] = min(dp[j], dp[j-i]+1)
print(dp[-1])

Submission status: Accepted

Solution code:
from itertools import count, takewhile, dropwhile
 
def dfs(n, max9, max6, d={0:0}):
    if n in d: return d[n]
  
    max9 = next(dropwhile(lambda x: x>n, (max9 / 9**i for i in count())))
    max6 = next(dropwhile(lambda x: x>n, (max6 / 6**i for i in count())))
    d[n] = min(dfs(n-max9, max9, max6), dfs(n-max6, max9, max6)) + 1
    return d[n]
 
n = int(input())
 
max9 = max(takewhile(lambda x: x<=n, (9**i for i in count())))
max6 = max(takewhile(lambda x: x<=n, (6**i for i in count())))
 
print(dfs(n, max9, max6))

Submission status: Accepted

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

    min_t = 100000
    for i in range(n+1):
        x, six = i, 0
        while x > 0:
            six += x % 6
            x //= 6

        y, nine = n - i, 0
        while y > 0:
            nine += y % 9
            y //= 9

        if six + nine < min_t:
            min_t = six + nine

    print(min_t)


if __name__ == '__main__':
    main()

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 //= 6
    t = N-i
    while t > 0:
        cc += t % 9
        t //= 9
    if res > cc:
        res = cc

print(res)