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

six = 1
while six <= N:
    six = six*6
    li.append(six)

nine = 1
while nine <= N:
    nine = nine*9
    li.append(nine)

INF = 10**10

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

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

Submission status: Accepted

Solution code:
N = int(input())

s = set()
a = 1
while a <= 100000:
    s.add(a)
    a *= 6
a = 1
while a <= 100000:
    s.add(a)
    a *= 9
s = sorted(s)

INF = float('inf')
dp = [INF] * (N+1)
dp[0] = 0
for i in range(N):
    for a in s:
        if i+a > N: break
        dp[i+a] = min(dp[i+a], dp[i] + 1)
print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())

ans = 10**10
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 abc099_c():
    ''' maspyさんお手本 '''
    import numpy as np
    N = int(input())

    coin = [6**n for n in range(10) if 6**n <= N]  # N以下の6の乗数
    coin += [9**n for n in range(10) if 9**n <= N]  # N以下の9の乗数

    dp = np.zeros(N+1, dtype=int)
    dp += 10**9
    dp[0] = 0

    for c in coin:
        # それぞれの額は9回以下なので
        # (6か9の倍数なので周期は最大9で、9回更新すれば十分？？)
        for _ in range(9):
            dp[c:] = np.minimum(dp[:-c]+1, dp[c:])

    ans = dp[N]
    print(ans)

abc099_c()

Submission status: Accepted

Solution code:
def abc099_c():
    ''' 解説PDF通り '''
    n = int(input())
    ans = n  # 初期値：ぜんぶ1円で引き出した最悪値

    # 6の乗数で支払う金額iを全探索
    for i in range(n+1):
        cc = 0
        t = i  # 6の乗数で支払う金額i
        while t > 0:
            cc += t % 6  # 最初に端数が入る、最後に6で割り切った倍数か乗数(なら1)が入る
            t //= 6
        t = n - i  # i以外を9の乗数で支払うとする
        while t > 0:
            cc += t % 9
            t //= 9
        ans = min(cc, ans)

    print(ans)

abc099_c()

Submission status: Accepted

Solution code:
N = int(input())

lst = [1]
lst += [ 6**i for i in range(1, 10) if 6**i <= 100000]
lst += [ 9**i for i in range(1, 10) if 9**i <= 100000]
lst.sort()

dp = list(range(N+1))

for i in range(1, N+1):
    temp = []
    for j in lst:
        if j <= i:
            temp.append(dp[i-j] + 1) 
    dp[i] = min(temp)
print(dp[N])

Submission status: Accepted

Solution code:
n = int(input())

res = 100000
for i6 in range(0, n+1, 6):
    c6, c9 = 0, 0
    i9 = n - i6
    while (i6 > 0):
        c6 = c6 + (i6%6)
        i6 = i6 // 6
    while (i9 > 0):
        c9 = c9 + (i9%9)
        i9 = i9 // 9

    if c6 + c9 < res:
        res = c6 + c9

print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def dfs(a,b,c):
  todo=[[]]
  ret=[]
  while len(todo)>0:
    t=todo.pop()
    l=len(t)
    if l==a:
      ret.append(t)
    else:
      s=0
      for i in range(1,l+1):
        s+=6**i*t[i-1]
      for i in range(b+1):
        if s+6**(l+1)*i<=c:
          tc=t.copy()
          tc.append(i)
          todo.append(tc)
  return ret
a=6
b=5
c=int(input())
l=dfs(a,b,c)
ans=c
for li in l:
  ansi=sum(li)
  now=c-sum([6**(i+1)*li[i]for i in range(len(li))])
  for i in range(1,7):
    ansi+=now%9
    now//=9
  ans=min(ans,ansi)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
INF = float('inf')
dp = [INF]* 100001
dp[0] = 0
cost = list()
cost.append(1)
i6 = 6
while(i6 <= 100000):
  cost.append(i6)
  i6 *= 6
i9 = 9
while(i9 <= 100000):
  cost.append(i9)
  i9 *= 9
cost.sort()
for i in range(1, 100001):
  for c in cost:
    if(i-c>=0):
      dp[i] = min(dp[i], dp[i-c]+1)
print(dp[N])

Submission status: Accepted

Solution code:
n = int(input())
#dp[j] = j￥を引き出すために必要な操作の最小回数
dp = [float('inf')]*(10**5+1)
dp[0] = 0
import math

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

    for k in range(int(math.log(i,6))+1):
        dp[i] = min(dp[i],dp[i-6**k]+1)
 
print(dp[n])
#print(dp[n-3:n+1])

Submission status: Accepted

Solution code:
n = int(input())

dp = [n] * 110000
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:
N = int(input())
tmp = [-1 for i in range(N + 1)]
tmp[0] = 0
s = [1]

for i in range(5):
    s.append(9** (i + 1))
for i in range(6):
    s.append(6** (i + 1))

for i in range(1, N+1):
    for j in range(N+1):
        if tmp[j] == i - 1:
            for k in range(12):
                a = j + s[k]
                if a <= N and tmp[a] == -1:
                    tmp[a] = i
    if tmp[N] > -1:
        break
print(i)

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    N=int(readline())
    
    dp=[0]*(100000+5)
    for n in range(1,100001):
        dp[n]=100000
        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])
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())

memo=[10**6]*100001
memo[0]=0

for i in range(100001):
    for j in range(1,8):
        if i+6**j>100000:
            continue
        memo[i+6**j]=min(memo[i]+1,memo[i+6**j])
        
    for j in range(1,7):
        if i+9**j>100000:
            continue
        memo[i+9**j]=min(memo[i]+1,memo[i+9**j])
    
    if i!=100000:
        memo[i+1]=min(memo[i]+1,memo[i+1])

print(memo[n])

Submission status: Accepted

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


def recursion(n, li):
    min_n = 10**9
    for i in li:
        if n - i < 0:
            continue
        num = dp[n - i]
        if min_n > num:
            min_n = num
    return min_n + 1


for i in range(1, 9):
    a = 6 ** i
    b = 9 ** i
    if a <= n:
        num_list.append(a)
    if b <= n:
        num_list.append(b)

for i in range(2, n+1):
    dp[i] = recursion(i, num_list)

print(dp[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 //= 6
	t = n - i
	while t > 0:
		cc += t % 9
		t //= 9
	if res > cc:
		res = cc
print(res)

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())

coin = [6**n for n in range(10) if 6**n <= N]
coin += [9**n for n in range(10) if 9**n <= N]

dp = np.zeros(N+1, dtype=np.int32)
dp += 10**9
dp[0] = 0

for c in coin:
  for _ in range(9):
    dp[c:] = np.minimum(dp[:-c] + 1, dp[c:])

answer = dp[-1]
print(answer)

Submission status: Accepted

Solution code:
# coding: utf-8

# https://atcoder.jp/contests/abc099/tasks
# 15:00-


def main():
    N = int(input())
    INF = 10**6

    moneys = [1]

    n = 1
    while 9**n <= N:
        moneys.append(9**n)
        n += 1

    n = 1
    while 6**n <= N:
        moneys.append(6**n)
        n += 1

    dp = [[INF] * (N+1) for _ in range(len(moneys))]
    for i in range(len(dp)):
        dp[i][0] = 0
    
    for i in range(len(dp)):
        for j in range(N+1):
            if j + moneys[i] <= N:
                dp[i][j+moneys[i]] = min(dp[i][j]+1, dp[i][j+moneys[i]])
                if i+1 < len(dp):
                    dp[i+1][j+moneys[i]] = min(dp[i][j]+1, dp[i+1][j+moneys[i]])
            if i+1 < len(dp):
                dp[i+1][j] = min(dp[i][j], dp[i+1][j])
    
    return dp[-1][-1]


print(main())

Submission status: Accepted

Solution code:
import sys
n = int(input())
dp=[sys.maxsize]*(n+1)
def beki(arg):
  res=0
  t=1
  while t < n:
    t=t*arg
    res+=1
  return res

dp[0]=0
a = beki(9)
b = beki(6)

for i in range(n):
  dp[i+1]=min(dp[i+1],dp[i]+1)
  for j in range(1,a+1):
    if i+9**j > n:
      break
    dp[i+9**j]=min(dp[i+9**j],dp[i]+1)
  for j in range(1,b+1):
    if i+6**j > n:
      break
    dp[i+6**j]=min(dp[i+6**j],dp[i]+1)
print(dp[n])

Submission status: Accepted

Solution code:
n = int(input())

b6 = 6
b9 = 5

dp = [[0] * (n + 1) for _ in range(1 + 1 + b6 + b9)]

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

for i in range(1, n + 1):
    for j in range(1, b9 + 1):
        dp[j + b6 + 1][i] = dp[b6 + j][i]
        if i >= 9 ** j:
            dp[j + b6 + 1][i] = min([
                dp[j + b6 + 1][i], 
                dp[j + b6 + 1][i - (9 ** j)] + 1
            ])

print(dp[-1][n])

Submission status: Accepted

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

i = 1
while 6**i < n+1:
    ary.append(6**i)
    i += 1
ary.sort()

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

for i in range(1,n+1):
    tmp = dp[i] + 1
    for j, aa in enumerate(ary):
        if i >= aa:
            tmp = min(tmp, dp[i-aa] + 1)
        else:
            break
    dp[i] = tmp
print(dp[n])

Submission status: Accepted

Solution code:
def dfs(i, n):
    if n < 6:
        return i + n
    k = 1
    while k * 6 <= n:
        k *= 6
    l = 1
    while l * 9 <= n:
        l *= 9
    return min(dfs(i + 1, n - k), dfs(i + 1, n - l))

N = int(input())
print(dfs(0, N))

Submission status: Accepted

Solution code:
n = int(input())

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

dp = [float('inf')]*101000
dp[0] = 0

for i in range(1, n+1):
    mins = float('inf')
    for a in ar:
        if i >= a:
            # i円の最小操作回数 = min(i-1円の最小操作回数+1, i-ar[j]円の最小操作回数+1
            mins = min(mins, min(dp[i-1] + 1, dp[i-a]+1))
    dp[i] = mins
print(dp[n])

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(read())
ans = n
for i in range(n + 1):
    cnt = 0
    v = i
    while v > 0:
        v, y = divmod(v, 6)
        cnt += y
    j = n - i
    while j > 0:
        j, y = divmod(j, 9)
        cnt += y
    if ans > cnt:
        ans = cnt
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

x = 6
while x < 100000:
    num.append(x)
    x *= 6

x = 9
while x < 100000:
    num.append(x)
    x *= 9

dp = [n] * 1100000
dp[0] = 0

for i in range(n):
    for j in num:
        dp[i + j] = min(dp[i + j], dp[i] + 1)

print(dp[n])

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


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

    A = []
    i = 1
    while True:
        if 6**i <= 100000:
            A.append(6**i)
            i += 1
        else:
            break
    A.sort(reverse=True)
    B = []
    i = 1
    while True:
        if 9**i <= 100000:
            B.append(9**i)
            i += 1
        else:
            break
    B.sort(reverse=True)

    ans = float("inf")
    for i in range(N+1):
        n_6, n_9 = i, N-i
        c_6 = 0
        for a in A:
            q, _, = divmod(n_6, a)
            c_6 += q
            n_6 -= a * q
        c_6 += n_6
        c_9 = 0
        for b in B:
            q, _, = divmod(n_9, b)
            c_9 += q
            n_9 -= b * q
        c_9 += n_9
        c = c_6 + c_9
        if c < ans:
            ans = c
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


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

    A = []
    i = 1
    while True:
        if 6**i <= 100000:
            A.append(6**i)
            i += 1
        else:
            break
    A.sort(reverse=True)
    B = []
    i = 1
    while True:
        if 9**i <= 100000:
            B.append(9**i)
            i += 1
        else:
            break
    B.sort(reverse=True)

    ans = float("inf")
    for i in range(N+1):
        n_6, n_9 = i, N-i
        c_6 = 0
        for a in A:
            while True:
                if a <= n_6:
                    n_6 -= a
                    c_6 += 1
                else:
                    break
        c_6 += n_6
        c_9 = 0
        for b in B:
            while True:
                if b <= n_9:
                    n_9 -= b
                    c_9 += 1
                else:
                    break
        c_9 += n_9
        c = c_6 + c_9
        if c < ans:
            ans = c
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def dfs(R, cnt):
    if R < 6:
        return cnt + R
    elif R < 9:
        return cnt + 1 + (R-6)
    else:
        c_6 = dfs(R-6, cnt+1)
        c_9 = dfs(R-9, cnt+1)
        return min(c_6, c_9)


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

    A = []
    i = 1
    while True:
        if 6**i <= 100000:
            A.append(6**i)
            i += 1
        else:
            break
    A.sort(reverse=True)
    B = []
    i = 1
    while True:
        if 9**i <= 100000:
            B.append(9**i)
            i += 1
        else:
            break
    B.sort(reverse=True)

    ans = float("inf")
    for i in range(N+1):
        n_6, n_9 = i, N-i
        c_6 = 0
        for a in A:
            while True:
                if a <= n_6:
                    n_6 -= a
                    c_6 += 1
                else:
                    break
        c_6 += n_6
        c_9 = 0
        for b in B:
            while True:
                if b <= n_9:
                    n_9 -= b
                    c_9 += 1
                else:
                    break
        c_9 += n_9
        c = c_6 + c_9
        if c < ans:
            ans = c
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
L = [1, 6, 9]

tmp = 6
while tmp < N:
    tmp *= 6
    L.append(tmp)
tmp = 9
while tmp < N:
    tmp *= 9
    L.append(tmp)

L.sort(reverse=True)


DP = [float('inf')] * 100001
DP[0] = 0
for i in range(1, 6):
    DP[i] = i
DP[6] = 1

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

print(DP[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=cc+t%6
        t=t//6
    t=n-i
    while t>0:
        cc=cc+t%9
        t=t//9
    if res>cc:
        res=cc

print(res)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

def main():
    N = int(readline())
    dp = [i for i in range(N+1)]

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

    print(dp[N])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
from math import floor, log

def main():
    N = int(readline())
    dp = [i for i in range(N+1)]
    for i in range(N):
        dp[i+1] = min(dp[i+1], dp[i]+1)
        log9 = floor(log(N-i, 9))
        for e in range(1, log9+2):
            if i + 9**e <= N:
	            dp[i+9**e] = min(dp[i+9**e], dp[i]+1)
        log6 = floor(log(N-i, 6))
        for e in range(1, log6+2):
            if i + 6**e <= N:
            	dp[i+6**e] = min(dp[i+6**e], dp[i]+1)
    
    print(dp[N])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
from math import floor, log

def main():
    N = int(readline())
    dp = [i for i in range(N+1)]

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
val=[]
cnt=0
for i in range(1,6,1):
    val.append(pow(9,i))
for i in range(1,7,1):
    val.append(pow(6,i))
val.append(1)
val.sort(reverse=True)
#print(val)
dp=[float("inf")]*(N+1)
dp[0]=0
for i in range(N+1):
    for j in range(len(val)):
        if val[j]<=i:
            dp[i]=min(dp[i],dp[i-val[j]]+1)
    #print(dp)
    #input()
print(dp[N])

Submission status: Accepted

Solution code:
n=int(input())
dp=[1000000]*(n+1)
dp[0]=0
for i in range(1,n+1):
    m=100000
    p=6
    q=9
    while p<=i:
        if m>dp[i-p]+1:
            m=dp[i-p]+1
        p*=6
    while q<=i:
        if m>dp[i-q]+1:
            m=dp[i-q]+1
        q*=9
    dp[i]=min(dp[i-1]+1,m)
print(dp[n])

Submission status: Accepted

Solution code:
import sys

N = int(input())

# n 円を引き出すための最小の引き出し回数

table = [i for i in range(0, N  + 1)]  # 1円ずつ引き出した場合

for base in (6, 9):  
  unit = base  # 引き出し単位
  while unit <= N:
    for i in range(unit, N + 1):
      table[i] = min(
        table[i],
        table[i - unit] + 1
      )
    
    unit *= base

print(table[N])

Submission status: Accepted

Solution code:
import math

N = int(input())

#dp[i+1]:i円引き出すまでの回数

I = math.floor(math.log(N, 6))
J = math.floor(math.log(N+1, 9))

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

for n in range(N):
    t_min = dp[n] + 1
    for i in range(1,I+1):
        if n+1 < 6**i:
            break
        t_min = min(t_min, dp[n-6**i+1]+1)
    for j in range(1,J+1):
        if n+1 < 9**j:
            break
        t_min = min(t_min, dp[n-9**j+1]+1)
    dp[n+1] = t_min

print(dp[N])

Submission status: Accepted

Solution code:
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


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

    weight = [1]
    pow6 = 6
    while pow6 <= W:
        weight.append(pow6)
        pow6 *= 6
    pow9 = 9
    while pow9 <= W:
        weight.append(pow9)
        pow9 *= 9

    N = len(weight)

    MAX_N = 15
    MAX_W = 100005
    INF = 1000000005
    dp = [[INF for _ in range(MAX_W)] for _ in range(MAX_N)]
    for i in range(N + 1):
        dp[i][0] = 0

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

    print(dp[N][W])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

A = []
for i in range(20):
    if 6**i<=N:
        A.append(6**i)
for i in range(1,20):
    if 9**i<=N:
        A.append(9**i)
AA = sorted(A,reverse=True)
#print(AA)
        
INF = float("inf")
dp=[INF]*(N+1)
dp[0]=0

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

Submission status: Accepted

Solution code:
# coding: utf-8
import numpy as np

n = int(input())

dp = [np.inf for _ in range(n+10)]
dp[0] = 0

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n= ii()
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)

Submission status: Accepted

Solution code:
n = int(input())
mo_9 =  [1]
mo_6 = [1]
roku = 1
while 6**roku <= n:
  mo_6.append(6**roku)
  roku += 1
kyuu = 1
while 9**kyuu <= n:
  mo_9.append(9**kyuu)
  kyuu += 1
mo_6 = list(reversed(mo_6))
mo_9 = list(reversed(mo_9))
ans = 10**6 +1
for i in range(n+1):
  a = i
  b = n-i
  ans_temp =  0
  for j in mo_6:
    ans_temp +=  a//j
    a =  a % j
  for j in mo_9:
    ans_temp += b//j
    b =  b % j
  ans = min(ans, ans_temp)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
l = list(i for i in range(n+1))
for i in range(n+1):
  for k in range(7):
    if i+6**k<=n:
      l[i+6**k] = min(l[i+6**k],l[i]+1)
 # print(l)
  for m in range(7):
    if i+9**m<=n:
      l[i+9**m] = min(l[i+9**m],l[i]+1)
  #print(l)
print(l[-1])

Submission status: Accepted

Solution code:
N = int(input())
INF = 10 ** 9
dp =  [INF] * (N + 1)
dp[0] = 0
for i in range(N):
    dp_i = dp[i]
    x = 1
    while N >= i + x:
        if dp[i+x] > dp_i + 1:
            dp[i+x] = dp_i + 1
        x *= 6
    x = 1
    while N >= i + x:
        if dp[i+x] > dp_i + 1:
            dp[i+x] = dp_i + 1
        x *= 9
print(dp[N])

Submission status: Accepted

Solution code:
N=int(input())
dp=[float("INF")]*(N+2)#i円払うのに必要な回数dp[i]
dp[0]=0#0円は0枚でよい
a,b,c=1,1,0
for i in range(1,N+1):
  if i==6*a:
    a*=6
  if i==9*b:
    b*=9
  dp[i]=min(dp[i],dp[i-1],dp[i-a],dp[i-b])+1
print(dp[N])

Submission status: Accepted

Solution code:
n=int(input())
ans=float("INF")
for i in range(n+1):
  d=0
  temp=n-i
  while (i>0):
    d+=i%6
    i//=6
  while(temp>0):
    d+=temp%9
    temp//=9
  ans=min(d,ans)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
ans=float("INF")
for i in range(n+1):
  d=0
  temp=i
  while (temp>0):
    d+=temp%6
    temp//=6
  temp=n-i
  while(temp>0):
    d+=temp%9
    temp//=9
  ans=min(d,ans)
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
dp=[float("INF")]*(n+1)
dp[0]=0
temp=6
cnt=0
while temp<=n:
  cnt+=1
  dp[temp]=1
  temp*=6
l=[0,0]
l[0]=cnt
temp=9
cnt=0
while temp<=n:
  cnt+=1
  dp[temp]=1
  temp*=9
l[1]=cnt
for j,v in zip(l,[6,9]):
  for i in range(j+1):
    h=pow(v,i)
    for d in range(h,n+1):
      dp[d]=min(dp[d],dp[d-h]+1)
print(dp[-1])

Submission status: Accepted

Solution code:
n = int(input())

dp = [0] + [100000]*n

ptn = [1]
_ = 1
while 6**_ < 100000:
    ptn.append(6**_)
    _ += 1

_ = 1
while 9**_ < 100000:
    ptn.append(9**_)
    _ += 1

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

Submission status: Accepted

Solution code:
N = int(input())
dp = list(range(N+1))
price = [1]
base = 1
while base<=100000:
    base *= 6
    price.append(base)
base = 1
while base<=100000:
    base *= 9
    price.append(base)

for i in range(1,N+1):
    for p in price:
        if p == i:
            dp[i] = 1
            break
        elif p < i:
            temp = dp[i-p]
            if temp+1 < dp[i]:
                dp[i] = temp+1
print(dp[N])

Submission status: Accepted

Solution code:
l_6 = []
_ = 1
while 6**_ < 100000:
    l_6.append(6**_)
    _ += 1
l_6.sort(reverse = 1)

l_9= []
_ = 1
while 9**_ < 100000:
    l_9.append(9**_)
    _ += 1
l_9.sort(reverse = 1)

n = int(input())

w = 0
z = []
for i in range(n+1):
    x = i
    for j in range(len(l_6)):
        while l_6[j] <= x:
            x -= l_6[j]
            w += 1
    else:
        w += x
    
    y = n-i
    for k in range(len(l_9)):
        while l_9[k] <= y:
            y -= l_9[k]
            w += 1
    else:
        w += y

    z.append(w)
    w = 0

print(min(z))

Submission status: Accepted

Solution code:
# solution

data=int(input())

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

dp[0]=0

for i in range(data+1):
    pow=1
    while pow<=data:
        dp[i]=min(dp[i],dp[i-pow]+1)
        pow*=6
    pow=1
    while pow<=data:
        dp[i]=min(dp[i],dp[i-pow]+1)
        pow*=9
print(dp[data])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
dp=[float("INF")]*(N+1)
dp[0]=0
six,nine=1,1
for i in range(1,N+1):
  if i==six*6:
    six*=6
  if i==nine*9:
    nine*=9
  dp[i]=min(dp[i-1],dp[i-six],dp[i-nine])+1
print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())
INF = 10 ** 6
dp = [INF] * (N + 1)

MONEY = []
i = 1
while i <= N:
    MONEY.append(i)
    i *= 6
i = 1
while i <= N:
    MONEY.append(i)
    i *= 9

MONEY.sort()
# print(MONEY)

for init in MONEY:
    dp[init] = 1


for i in range(1, N + 1):
    for plus in MONEY:
        if i + plus <= N:
            dp[i + plus] = min(dp[i] + 1, dp[i + plus])
# print(dp)
print(dp[N])

Submission status: Accepted

Solution code:
import math
n = int(input())
if n < 6:
  print([0,1,2,3,4,5][n])
  quit()
ans = 10**6
m = int(math.log(n)/math.log(6))
for i in range(int(n/(6**m))+1):
  for j in range(6**m):
    s = i*(6**m)
    cnt = i
    lst = []
    for k in range(m):
      time = (j//(6**k)) % 6
      cnt += time
      s += time*(6**k)
      lst.append(time)
    if s <= n:
      N = n - s
      for k in range(6):
        cnt += (N//(9**k)) % 9
      ans = min(cnt,ans)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

l = [1] + [pow(6,i) for i in range(1,15)] + [pow(9,i) for i in range(1,10)]
l.sort()
dp = [10**10] * (n+1)
dp[0] = 0
for li in l:
  for i in range(n - li + 1):
    dp[i + li] = min(dp[i + li], dp[i] + 1)
print(dp[n])

Submission status: Accepted

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

for cnt in [6, 9]:
    tmp = cnt
    while tmp <= 10 ** 5:
        upper.append(tmp)
        tmp *= cnt

dp = [float("inf")] * (10 ** 5 + 1)
dp[0] = 0
for u in upper:
    dp[u] = 1

for i in range(2, N + 1):
    for u in upper:
        if i - u > 0:
            tmp = dp[i - u] + 1
            if tmp < dp[i]:
                dp[i] = tmp

print(dp[N])

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest

sys.setrecursionlimit(100**3)

def rec(n, dp):
	if n <= 1:
		return n
	if dp[n] < float('inf'):
		return dp[n]
	pow6 = 6
	pow9 = 9
	dp[n] = min(n, dp[n])
	while n >= pow6:
		dp[n] = min(dp[n], rec(n-pow6, dp) + 1)
		pow6 *= 6
	while n >= pow9:
		dp[n] = min(dp[n], rec(n-pow9, dp) + 1)
		pow9 *= 9
	return dp[n]

def resolve():
	n = int(input())
	dp = [float('inf')]*(n+1)
	print(rec(n, dp))
resolve()

Submission status: Accepted

Solution code:
N=int(input());t={0:0}
for i in range(1,N+1):
 x,j=N,0
 while 6**j<=i:x=min(x,t[i-6**j],t.get(i-9**j,N));j+=1
 t[i]=x+1
print(t[N])

Submission status: Accepted

Solution code:
N=int(input());t=[0]+[N]*N
for i in range(1,N+1):
 x,a,b=t[i-1],6,9
 while a<=i:x=min(x,t[i-a],t[i-b]if b<=i else N);a*=6;b*=9
 t[i]=x+1
print(t[N])

Submission status: Accepted

Solution code:
N = int(input())
t = list(range(N+1))
for i in range(2, N+1):
    x = t[i-1] + 1
    p6, p9 = 6, 9
    while i-p6 >= 0:
        x = min(x, t[i-p6] + 1)
        p6 *= 6
    while i-p9 >= 0:
        x = min(x, t[i-p9] + 1)
        p9 *= 9
    t[i] = x
print(t[N])

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    c = [pow(6, i) for i in range(7)] + [pow(9, i) for i in range(1, 6)]
    c.sort()
    dp = [[0] * (N+1) for _ in range(len(c))]
    for j in range(1, N+1):
        dp[0][j] = j
    for i in range(1, len(c)):
        for j in range(1, N+1):
            dp[i][j] = dp[i-1][j]
            if j - c[i] >= 0:
                dp[i][j] = min(dp[i][j], dp[i][j-c[i]] + 1)
    r = 10**6
    for i in range(len(c)):
        r = min(r, dp[i][-1])
    print(r)
main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = [0] * (N + 1)
    s, n = 1, 1
    for i in range(1, N + 1):
        if s * 6 == i:
            s *= 6
        if n * 9 == i:
            n *= 9
        A[i] = min(A[i - 1] + 1, A[i - n] + 1, A[i - s] + 1)
    return A[N]
        

print(main())

Submission status: Accepted

Solution code:
n = int(input())
choice = [1]
for i in range(1,7):
    choice.append(6**i)
    choice.append(9**i)
dp = [float('INF')]*(10**5+1)
dp[0] = 0
for i in range(1,10**5+1):
    for j in choice:
        if i<j:
            continue
        else:
            dp[i] = min(dp[i],dp[i-j]+1)
print(dp[n])

Submission status: Accepted

Solution code:
import math
N = int(input())
dp = [10 ** 4 for i in range(N+1)]
dp[0] = 0
for i in range(1,N+1):
    dp[i] = min(dp[i],dp[i-1]+1)

    a = 1
    while(i - 6 ** a >= 0):
        #process
        dp[i] = min(dp[i],dp[i-6**a]+1)
        a += 1
    
    b = 1
    while(i - 9 ** b >= 0):
        #process
        dp[i] = min(dp[i],dp[i-9**b]+1)
        b += 1
    
print(dp[N])

Submission status: Accepted

Solution code:
from itertools import product
n= int(input())

ls6 = []
ls9 = [1]
for i in range(1,8):
    ls6.append(6**i)
    ls9.append(9**i)
ls9.sort(reverse=True)
l= len(ls6)
ans = 10**9
for s in product([0,1,2,3,4,5],repeat=l):
    cnt = 0
    t=n
    for i,c in enumerate(s):
        t-= ls6[i]*c
        cnt+=c
    if t<0:continue
    for num in ls9:
        q,t = divmod(t,num)
        cnt+=q
    if t==0:ans=min(ans,cnt)
print(ans)