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 sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()

dp = [INF]*(100001)
dp[0] = 0
dp[1] = 1
dp[6] = 1
dp[6**2] = 1
dp[6**3] = 1
dp[6**4] = 1
dp[6**5] = 1
dp[6**6] = 1
dp[9] = 1
dp[9**2] = 1
dp[9**3] = 1
dp[9**4] = 1
dp[9**5] = 1

for i in range(N):
	dp[i+1] = min(dp[i+1], dp[i]+1)
	if i+6 > N:
		continue
	dp[i+6] = min(dp[i+6], dp[i]+1)
	if i+9 > N:
		continue
	dp[i+9] = min(dp[i+9], dp[i]+1)
	if i+6**2 > N:
		continue
	dp[i+6**2] = min(dp[i+6**2], dp[i]+1)
	if i+9**2 > N:
		continue
	dp[i+9**2] = min(dp[i+9**2], dp[i]+1)
	if i+6**3 > N:
		continue
	dp[i+6**3] = min(dp[i+6**3], dp[i]+1)
	if i+9**3 > N:
		continue
	dp[i+9**3] = min(dp[i+9**3], dp[i]+1)
	if i+6**4 > N:
		continue
	dp[i+6**4] = min(dp[i+6**4], dp[i]+1)
	if i+9**4 > N:
		continue
	dp[i+9**4] = min(dp[i+9**4], dp[i]+1)
	if i+6**5 > N:
		continue
	dp[i+6**5] = min(dp[i+6**5], dp[i]+1)
	if i+6**6 > N:
		continue
	dp[i+6**6] = min(dp[i+6**6], dp[i]+1)
	if i+9**5 > N:
		continue
	dp[i+9**5] = min(dp[i+9**5], dp[i]+1)

# for i in range(N+1):
# 	print(i, dp[i])
print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())

dp = [0] * (N+1)

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

Submission status: Accepted

Solution code:
N = int(input())
dp = [0]*(100010)
dp[0] = 0
#dp[N] : N円払うのに必要な最小枚数
#dp[N] = min{1+dp[N-1],1+dp[N-6],1+dp[N-9],1+dp[N-6^2],...}

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

Submission status: Accepted

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

a=[0]*(N+1)
for i in range(1,N+1):
    k=[a[i-1]]
    for j in range(1,10):
        x=i-6**j
        if x<0: break
        k.append(a[x])
        
    for j in range(1,10):
        x=i-9**j
        if x<0: break
        k.append(a[x])
    
    a[i]=min(k)+1


print(int(a[N]))

Submission status: Accepted

Solution code:
N = int(input())
dp = [0 for i in range(N+1)]
dp[1] = 1
kazu = [1]
i = 6
while i <= N:
    kazu.append(i)
    i*=6
i = 9
while i <= N:
    kazu.append(i)
    i*=9
kazu.sort()
kazulazor = len(kazu)
temp = [1]
lentemp = 1
index = 1
for i in range(2, N+1):
    kouho = []
    if index < kazulazor and i == kazu[index]:
        temp.append(i)
        index += 1
        lentemp += 1
    for j in range(lentemp):
        kouho.append(dp[i-temp[j]]+1)
    dp[i] = min(kouho)
print(str(dp[N]))

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    target = int(input())
    withdraw_counts = [0] * (target + 1)

    for i in range(target + 1):
        if i < 6:
            withdraw_counts[i] = i
        elif i < 9:
            withdraw_counts[i] = i - 5
        else:
            needed_withdraw_counts = [withdraw_counts[i-1]]
            exp_n = 1
            while 6 ** exp_n <= i:
                needed_withdraw_counts.append(withdraw_counts[i - 6 ** exp_n])
                exp_n += 1
            exp_n = 1
            while 9 ** exp_n <= i:
                needed_withdraw_counts.append(withdraw_counts[i - 9 ** exp_n])
                exp_n += 1
            withdraw_counts[i] = min(needed_withdraw_counts) + 1
    print(withdraw_counts[target])

Submission status: Accepted

Solution code:
# not solved only by myself
N = int(input())

def get_nums(wa,ar):
    ar = sorted(ar,reverse=True)
    tmp = 0
    for a in ar:
        tmp += wa // a
        wa %= a
    return tmp + wa


nines = []
tmp = 9
while tmp <= N:
    nines.append(tmp)
    tmp *= 9

sixes = []
tmp = 6
while tmp <= N:
    sixes.append(tmp)
    tmp *= 6



res = N
for t in range(0,N + 1):
    hoge = get_nums(t,sixes) + get_nums(N - t,nines)
    res = min(res,hoge)

print(res)

Submission status: Accepted

Solution code:
N = int(input())

memo = {i:i for i in range(6)}
def f(n):
    tmp = memo.get(n,None)
    if tmp != None:
        return tmp
    i,j = 0,0
    a,b = n,n
    while a >= 6:
        i += 1
        a //= 6
    while b >= 9:
        j += 1
        b //= 9
    ret = min(1+f(n-6**i),1+f(n-9**j))
    memo[n] = ret
    return ret

print(f(N))

Submission status: Accepted

Solution code:
N = int(input())
a = [1]
t = 6
while t <= N:
    a.append(t)
    t *= 6
t = 9
while t <= N:
    a.append(t)
    t *= 9
INF = 10 ** 9
dp = [0] + [INF for _ in range(N)]
for i in range(1, N + 1):
    for x in a:
        if x <= i and dp[i - x] + 1 < dp[i]:
            dp[i] = dp[i - x] + 1
print(dp[N])

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())

N = int(stdin.readline())
large = float('inf')
memo = {}
def cal_count(total):
    global memo
    if total in memo: return memo[total]
    if total < 0: return large
    if total == 0: return 0
    cans = []
    for i in range(1, 8):
        if 6 ** i > total: break
        cans.append(cal_count(total - 9 ** i))
        cans.append(cal_count(total - 6 ** i))
    cans.append(cal_count(total - 1))
    res = min(cans) + 1
    memo[total] = res
    return res
cnt = cal_count(N)
print(cnt)

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(N+1):
  for j in [6**i for i in range(7)]:
    if i+j <= N:
      dp[i+j] = min(dp[i+j],dp[i]+1)
  for j in [9**i for i in range(1,6)]:
    if i+j <= N:
      dp[i+j] = min(dp[i+j],dp[i]+1)

print(dp[-1])

Submission status: Accepted

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

for i in range(N+1):
  for j in [6**i for i in range(7)]:
    if i+j <= N:
      dp[i+j] = min(dp[i+j],dp[i]+1)
  for j in [9**i for i in range(6)]:
    if i+j <= N:
      dp[i+j] = min(dp[i+j],dp[i]+1)

print(dp[-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

def fun(n):
  if n == 0:
    return 0
  elif dp[n] != 0:
    return dp[n]
  
  ans = N
  for i in [6**k for k in range(7)]:
    if i <= n:
      ans = min(ans, fun(n-i) + 1)
  for j in [9**l for l in range(6)]:
    if j <= n:
      ans = min(ans, fun(n-j) + 1)
  
  dp[n] = ans
  return dp[n]

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

Submission status: Accepted

Solution code:
N = int(input())

def fun(n,x):
  i = 0
  while(n > 0):
    i += n % x
    n //= x
  return i

ans = N

for j in range(N+1):
  ans = min(ans,fun(j,6)+fun(N-j,9))
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()
    ans = float("inf")
    for i in range(n+1):
        m = 0
        k = i
        while k > 0:
            m += k%6
            k //= 6
        k = n-i
        while k > 0:
            m += k%9
            k //= 9
        if m < ans:
            ans = m
    print(ans)
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#I
def I_():
    return

#J
def J():
    return

#Solve
if __name__ == "__main__":
    A()

Submission status: Accepted

Solution code:
import bisect

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

from functools import lru_cache


@lru_cache(maxsize=1000)
def six_nine(n):
    if n < 6:
        return n
    else:
        six = six_list[bisect.bisect_right(six_list, n) - 1]
        nine = nine_list[bisect.bisect_right(nine_list, n) - 1]
        return min(n // six + six_nine(n % six), 1 + six_nine(n - nine))


if __name__ == '__main__':
    x = int(input())
    print(six_nine(x))

Submission status: Accepted

Solution code:
import bisect
from functools import lru_cache

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


@lru_cache(maxsize=1000)
def six_nine(n):
    if n < 6:
        return n
    else:
        six = six_list[bisect.bisect_right(six_list, n) - 1]
        nine = nine_list[bisect.bisect_right(nine_list, n) - 1]
        return min(n // six + six_nine(n % six), 1 + six_nine(n - nine))


if __name__ == '__main__':
    x = int(input())
    print(six_nine(x))

Submission status: Accepted

Solution code:
import bisect

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


def six_nine(n):
    if n < 6:
        return n
    else:
        six = six_list[bisect.bisect_right(six_list, n) - 1]
        nine = nine_list[bisect.bisect_right(nine_list, n) - 1]
        return min(n // six + six_nine(n % six), 1 + six_nine(n - nine))


if __name__ == '__main__':
    x = int(input())
    print(six_nine(x))

Submission status: Accepted

Solution code:
import bisect


def six_nine(n):
    if n < 6:
        return n
    else:
        six = six_list[bisect.bisect_right(six_list, n) - 1]
        nine = nine_list[bisect.bisect_right(nine_list, n) - 1]
        return min(n // six + six_nine(n % six), 1 + six_nine(n - nine))


if __name__ == '__main__':
    x = int(input())
    six_list = [6 ** i for i in range(7)]
    nine_list = [9 ** i for i in range(6)]
    print(six_nine(x))

Submission status: Accepted

Solution code:
import bisect

x = int(input())
six_list = [6 ** i for i in range(7)]
nine_list = [9 ** i for i in range(6)]


def six_nine(n):
    if n < 6:
        return n
    else:
        six = six_list[bisect.bisect_right(six_list, n) - 1]
        nine = nine_list[bisect.bisect_right(nine_list, n) - 1]
        return min(n // six + six_nine(n % six), 1 + six_nine(n - nine))


print(six_nine(x))

Submission status: Accepted

Solution code:
import bisect

x = int(input())
six_list = [6 ** i for i in range(7)]
nine_list = [9 ** i for i in range(6)]


def six_nine(n):
    if n == 0:
        return 0
    else:
        six = six_list[bisect.bisect_right(six_list, n) - 1]
        nine = nine_list[bisect.bisect_right(nine_list, n) - 1]
        return min(n // six + six_nine(n % six), 1 + six_nine(n - nine))


print(six_nine(x))

Submission status: Accepted

Solution code:
n = int(input())

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

import bisect

def six_nine(n):
  if n == 0:
    return 0
  else:
    six = six_list[bisect.bisect_right(six_list, n) - 1]
    nine = nine_list[bisect.bisect_right(nine_list, n) - 1]
    return min(n // six + six_nine(n % six), 1 + six_nine(n - nine))


print(six_nine(n))

Submission status: Accepted

Solution code:
L = [1, 6, 36, 216, 1296, 7776, 46656, 9, 81, 729, 6561, 59049]

N = int(input())

dp = [float("inf") for i in range(200000)]
dp[0] = 0
for i in range(N + 1):
	for j in L:
		if dp[i] + 1 <= dp[i + j]:
			dp[i + j] = dp[i] + 1
print(dp[N])

Submission status: Accepted

Solution code:
# https://qiita.com/_-_-_-_-_/items/34f933adc7be875e61d0
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = s_inpl()   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = inpl()	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import math
import copy
from collections import defaultdict, Counter
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

N = i_inpl()
dp = [INF for _ in range(N+1)]

dp[0] = 0

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

print(dp[N])

Submission status: Accepted

Solution code:
# https://qiita.com/_-_-_-_-_/items/34f933adc7be875e61d0
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = s_inpl()   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = inpl()	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import math
import copy
from collections import defaultdict, Counter
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

N = i_inpl()
dp = [INF for _ in range(N+1)]

dp[0] = 0

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

print(dp[N])

Submission status: Accepted

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

for i in range(1,N+1):
    for p in range(N+1):
        p = 6**p
        if p > N:
            break
        dp[i] = min(dp[i],dp[i-p]+1)
    for p in range(N+1):
        p = 9**p
        if p > N:
            break
        dp[i] = min(dp[i],dp[i-p]+1)

print(dp[N])

Submission status: Accepted

Solution code:
from collections import defaultdict
from string import ascii_uppercase
import sys, bisect
stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

N = read_int()[0]

items = [1]
Nd6 = 0
while True:
    if N // (6**(Nd6 + 1)) > 0:
        Nd6 += 1
        items.append(6 ** Nd6)
    else: break

Nd9 = 0
while True:
    if N // (9 ** (Nd9 + 1)) > 0:
        Nd9 += 1
        items.append(9 ** Nd9)
    else: break

items.sort()

dp = [0 for _ in range(N + 1)]
def solve():
    for i in range(N):
        for itm in items:
            if i + itm < N + 1:
                if dp[i + itm] == 0:
                    dp[i + itm] =dp[i] + 1
                else:
                    dp[i + itm] = min(dp[i + itm], dp[i] + 1)

    return dp[N]
  

if __name__ == "__main__":
    print(solve())

Submission status: Accepted

Solution code:
from collections import Counter
from functools import reduce
import fractions
import math
import statistics
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]  # LIST INT
def LF(): return [float(x) for x in sys.stdin.readline().split()]  # LIST FLOAT
def LS(): return sys.stdin.readline().split()  # LIST STRING
def MI(): return map(int, sys.stdin.readline().split())  # MAP INT
def II(): return int(sys.stdin.readline())  # INPUT INT
def IS(): return input()  # INPUT STRING
def P(x): return print(x)
def C(x): return Counter(x)
def GCD_LIST(numbers):  # greatest common divisor
    return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers):  # least common multiple
    return reduce(LCM, numbers)
def LCM(m, n):
    return (m * n // fractions.gcd(m, n))


# n = II()
# one = [1]
# six = [6 ** i for i in range(1, 6+1)]
# nine = [9 ** i for i in range(1, 5+1)]
# numbers = one + six + nine
# numbers.sort(reverse=True)

N = int(input())
dp = [INF] * 100001
dp[0], dp[1] = 0, 1
L = [1, 6, 36, 216, 1296, 7776, 46656, 9, 81, 729, 6561, 59049]
# dp[n]は，n円を引き出す最小引き出し回数
for i in range(2, 100001):
    for j in range(len(L)):
        if i-L[j] >= 0:
            dp[i] = min(dp[i-L[j]]+1, dp[i])
# 100円を引き出す時，まず，100-L[0] = 100-1=99で1円でのみで引き出すことを考える
# dp[100]にまずmin(dp[99]+1，INF)で99円引き出すための最小引き出し回数に1をたす（1円引き出す
# を考える
# 次に，その値と，94円から引き出すための最小回数+1とさっきのdp[99]を比較して，最小値を更新する
# 100000 * 10くらい 1000000くらい
print(dp[N])

Submission status: Accepted

Solution code:
def sum_base10to(n, b):
    if n // b:
        return sum_base10to(n // b, b) + n % b
    return n % b


n = int(input())
i = 0
res = n
for i in range(n + 1):
    cc = sum_base10to(i, 6) + sum_base10to(n - i, 9)
    if cc < res:
        res = cc
print(res)

Submission status: Accepted

Solution code:
N = int(input())
dp = [float('inf')]*100001
dp[0],dp[1] = 0,1
L = [1,6,36,216,1296,7776,46656,9,81,729,6561,59049]
for i in range(2,100001):
  for j in range(len(L)):
    if i-L[j] >= 0:
      dp[i] = min(dp[i-L[j]]+1,dp[i])
print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())
l = [1,6,9,36,81,216,729,1296,6561,7776,46656,59049]
dp = [N]*(N+1)
dp[0]=0

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import math
from collections import defaultdict
 
N = int(input())
 
memo = defaultdict(lambda: -1)
memo[0] = 0
def recursive(n):
    if memo[n] != -1:
        return memo[n]
    
    min_num_operation = n
    
    index = 0
    temp_n = n
    while temp_n > 0:
        if temp_n % 9 == 0:
            index += 1
            temp_n //= 9
        else:
            index += int(math.log(temp_n, 9))
            break
    if index > 0:
        min_num_operation = min(min_num_operation, 1 + recursive(int(n - math.pow(9, index))))
        
    index = 0
    temp_n = n
    while temp_n > 0:
        if temp_n % 6 == 0:
            index += 1
            temp_n //= 6
        else:
            index += int(math.log(temp_n, 6))
            break
    if index > 0:
        min_num_operation = min(min_num_operation, 1 + recursive(int(n - math.pow(6, index))))
        
    memo[n] = min_num_operation
    
    return min_num_operation
 
print(recursive(N))

Submission status: Accepted

Solution code:
N = int(input())

ms = set([1])
i = 1
while True:
    m = 6**i
    if m > N:
        break
    ms.add(m)
    i += 1
i = 1
while True:
    m = 9**i
    if m > N:
        break
    ms.add(m)
    i += 1

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

Submission status: Accepted

Solution code:
N = int(input())
INF = 10**9
dp = [INF]*(N+1)
dp[0] = 0
num6 = [6**i for i in range(1, 10)]
num9 = [9**i for i in range(1, 7)]
S = sorted([1] + num6 + num9)

for i in range(1, N+1):
    for j in S:
        if j > i:
            break
        else:
            dp[i] = min(dp[i], dp[i-j]+1)

print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())
INF = 10**9
dp = [INF]*(N+1)
dp[0] = 0
num6 = [6**i for i in range(1, 10)]
num9 = [9**i for i in range(1, 7)]
S = sorted([1] + num6 + num9)

for i in range(1, N+1):
    tmp = INF
    for j in S:
        if j > i:
            break
        else:
            dp[i] = min(tmp, dp[i-j]+1)
            tmp = dp[i]

print(dp[N])

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator


inf = float('inf')


# globals
N = 0


def set_inputs():
    global N
    N = get_int()
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    # ----------MAIN----------
    dp = [0] * (N + 1)
    ops = [
        1,
        6 ** 1, 6 ** 2, 6 ** 3, 6 ** 4, 6 ** 5, 6 ** 6,
        9 ** 1, 9 ** 2, 9 ** 3, 9 ** 4, 9 ** 5
    ]
    for i in range(1, N + 1):
        dp[i] = min(dp[i-j] for j in ops if i - j >= 0) + 1
    print(dp[N])
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types):
    if len(types) == 1:
        return [types[0](input()) for _ in range(n)]
    return zip(*(
        [t(x) for t, x in zip(types, input().split())]
        for _ in range(n)
    ))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
possible=[1,6,9,6**2,6**3,6**4,6**5,6**6,9**2,9**3,9**4,9**5]
dp=[10**18]*(10**5+1)
dp[0]=0
n=int(input())
for i in range(1,n+1):
  for j in possible:
    if i-j>=0:
      dp[i]=min(dp[i],1+dp[i-j])
print(dp[n])

Submission status: Accepted

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

for i in range(1,7):
  ls.append(6**i)
  ls.append(9**i)
dp = [float('inf') for i in range(n+2)]
dp[0] = 0

#円の総合計
for i in range(1,n+1):
  for j in ls:
    if i-j>=0:
      dp[i] = min(dp[i-1]+1, dp[i-j]+1,dp[i])
    else:
      dp[i] = min(dp[i-1]+1,dp[i])
print(dp[n])

Submission status: Accepted

Solution code:
n=int(input())

ls=set([1])
i=1
while 6**i<=100000:
  ls.add(6**i)
  i+=1
i=1
while 9**i<=100000:
  ls.add(9**i)
  i+=1

dp = [float("inf") for i in range(n+2)]
dp[0] = 0
ls=list(ls)
#円の総合計
for i in range(n+2):
  #額面のコインの種類
  for j in range(len(ls)):
    if i+ls[j]<=n:
      dp[i+ls[j]] = min(dp[i]+1, dp[i+ls[j]-1]+1,dp[i+ls[j]])
print(dp[n])

Submission status: Accepted

Solution code:
n=int(input())

ls=set([1])
i=1
while 6**i<=100000:
  ls.add(6**i)
  i+=1
i=1
while 9**i<=100000:
  ls.add(9**i)
  i+=1

dp = [float("inf") for i in range(n+2)]
dp[0] = 0

#円の総合計
for i in range(n+1):
  #額面のコインの種類
  for j in ls:
    if i + j <= n:
      dp[i+j] = min(dp[i+j], dp[i]+1)
print(dp[n])

Submission status: Accepted

Solution code:
n = int(input())
coins = [1]
t = 6 
while t <= n:
    coins.append(t)
    t *= 6

t = 9
while t <= n:
    coins.append(t)
    t *= 9

coins.sort()

dp = [ float("inf") for _ in range(n+10) ]
dp[0] = 0

for i in range(n+1):
    for c in coins:
        if i + c > n:
            continue
        dp[i+c] = min(dp[i+c], dp[i]+1)

print(dp[n])

Submission status: Accepted

Solution code:
N= int(input())
_l = [1, 6, 6**2, 6**3, 6**4, 6**5, 6**6, 6**7, 9, 9**2, 9**3, 9**4, 9**5, 9**6]
_l.sort()
#print(_l)

answer=[0]*(N+1)

for i in range(1, N+1):
  answer[i] = min([answer[i-l] +1 if i-l>=0 else 1000000 for l in _l])

print(answer[N])

Submission status: Accepted

Solution code:
n = int(input())
dp = [10**9+7]*(n+1)
dp[0] = 0
for i in range(1,n+1):
    dp[i] = dp[i-1] + 1
    j = 6
    while i-j >= 0:
        dp[i] = min(dp[i], dp[i-j]+1)
        j *= 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 = [float("inf")]*(n+1)
dp[0] = 0
for i in range(n):
	j = 0
	while i+6**j <= n:
		dp[i+6**j] = min(dp[i+6**j],dp[i]+1)
		j += 1
	k = 0
	while i+9**k <= n:
		dp[i+9**k] = min(dp[i+9**k],dp[i]+1)
		k += 1
print(dp[n])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

n = int(input())

get = []
for i in range(10):
  npow6 = 6**(i+1)
  npow9 = 9**(i+1)
  if npow6 <= 100000:
    get.append(npow6)
  if npow9 <= 100000:
    get.append(npow9)
  
get = sorted(get)

memo = [-1] * 110000
for i in range(6):
  memo[i] = i
  
def dfs(money):
  if memo[money] != -1:
    return memo[money]
  ret = 110000
  for g in get:
    if g > money:
      continue
    ret0 = dfs(money-g) + 1
    ret = min(ret, ret0)
  memo[money] = ret
  return ret

print(dfs(n))

Submission status: Accepted

Solution code:
def solve(n):
 dp = [9999999]*100005
 dp[0] = 0
 for i in range(1,n+1):
  dp[i] = min(dp[i],dp[i-1]+1)
  tmp = 6
  
  while (i-tmp >= 0):
    dp[i] = min(dp[i],dp[i-tmp]+1)
    tmp *= 6
  tmp2 = 9
  while (i-tmp2 >= 0):
    dp[i] = min(dp[i],dp[i-tmp2]+1)
    tmp2 *= 9
 print(dp[n])

n = int(input())
solve(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(ans)

Submission status: Accepted

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

    for i in range(1,x+1):

        dp[i] = 1 + dp[i-1]

        sup = 0
        while 1:
            if i - 6**sup < 0:
                break
            tmp = 1 + dp[i-6**sup]
            dp[i] = min(dp[i],tmp)
            sup += 1

        sup = 0
        while 1:
            if i - 9**sup < 0:
                break
            tmp = 1 + dp[i-9**sup]
            dp[i] = min(dp[i],tmp)
            sup += 1

    print(dp[x])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())

dp = [0] * (n + 1)

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

Submission status: Accepted

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

def solve():
	N = int(input())
	INF = 100000

	# dp[N] := N円にするのに必要な枚数の最小値
	dp = [INF] * (N+10)
	dp[0] = 0
	for n in range(1, N+1):
		# 1円使うとき
		dp[n] = min(dp[n], dp[n-1]+1)

		power = 6
		while (power <= n):
			dp[n] = min(dp[n], dp[n-power]+1)
			power *= 6
		
		power = 9
		while (power <= n):
			dp[n] = min(dp[n], dp[n-power]+1)
			power *= 9
	
	print(dp[N])



if __name__ == "__main__":
	solve()

Submission status: Accepted

Solution code:
n = int(input())

def ans(x):
    dp = [i for i in range(x+1)]
    yenlist = [6,9]
    for i in yenlist:
        k = 1
        while i**k <= x:
            q = i**k
            for j in range(x+1-q):
                dp[j+q] = min(dp[j]+1,dp[j+q]) 
            k += 1
    return dp[x]

answer = ans(n)
print(answer)

Submission status: Accepted

Solution code:
N = int(input())
dp = [0 for i in range(N+1)]
dp[1] = 1
roku = 0
kyu = 0
for i in range(2, N+1):
    if i == 6**(roku+1):
        roku += 1
    if i == 9**(kyu+1):
        kyu += 1
    kouho = [1]
    for j in range(roku):
        kouho.append(6**(j+1))
    for j in range(kyu):
        kouho.append(9**(j+1))
    size = len(kouho)

    small = 1000000
    for j in range(size):
        if dp[i - kouho[j]] + 1 < small:
            small = dp[i - kouho[j]] + 1
    dp[i] = small
print(str(dp[N]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())

lst = []
for i in range(7):
    lst.append(6**i)
for i in range(1, 6):
    lst.append(9**i)

dp = [0]*100001
for i in range(1, n+1):
    candi = []
    for j in lst:
        if i >= j:
            candi.append(dp[i-j]+1)
    dp[i] = min(candi)
print(dp[i])

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

"""
N = 6**i + 9**j
とする。

"""

N = I()

smalls = []
bigs = []
for i in range(10**5):
    small = 6**i
    big = 9**i

    if small <= N:
        smalls.append(small)
    if big <= N:
        bigs.append(big)
    if small > N:
        break

smalls = sorted(smalls, reverse=True)
bigs = sorted(bigs, reverse=True)
#  print('smalls, bigs', smalls, bigs)

result = 10**13
for i in range(0, N+1):
    #  print('i', i)
    # i は6だけで払う分
    small_n = i
    big_n = N - i

    small_idx = 0
    big_idx = 0

    small_count, big_count = 0, 0
    while small_n != 0:
        if smalls[small_idx] > small_n:
            small_idx += 1
            continue
        small_n -= smalls[small_idx]
        small_count += 1

    while big_n != 0:
        if bigs[big_idx] > big_n:
            big_idx += 1
            continue
        big_n -= bigs[big_idx]
        big_count += 1
    #  print('small_count, big_count', small_count, big_count)
    result = min(result, small_count+big_count)

print(result)