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:
from _collections import deque
from _ast import Num


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
from collections import deque
from math import sqrt
from math import floor
# https://atcoder.jp/contests/abc107/tasks/arc101_a
# C - Candles
"""
need to consider the case that ticket is not enough to lower everything
"""
N = gi()
cs = []
cs.append(1)
b6 = 6
while (b6 <= 1e5):
    cs.append(b6)
    b6 *= 6
b9 = 9
while (b9 <= 1e5):
    cs.append(b9)
    b9 *= 9
ans = [N] * (N + 1)
ans[0] = 0

for i in range(1, N + 1):
    for v in cs:
        if i >= v:
            ans[i] = min(ans[i], ans[i - v] + 1)

print(ans[N])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
dp = [2**60]*(100000+n)
dp[0] = 0
for i in range(n+1):
    for j in range(7):
        dp[i] = min(dp[i-6**j]+1,dp[i])
    for k in range(6):
        dp[i] = min(dp[i],dp[i-9**k]+1)
print(dp[n])

Submission status: Accepted

Solution code:
n = int(input())
MAXN = 110000

f_inf = float('inf')
dp = [f_inf] * (MAXN+n)

dp[0] = 0

for i in range(1, n+2):
    for j in range(7):
        dp[i] = min(dp[i], dp[i-pow(6, j)]+1)
    for k in range(6):
        dp[i] = min(dp[i], dp[i-pow(9, k)]+1)

print(dp[n])

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc099/tasks/abc099_c
# 典型的なコイン問題

# 引き出す金額の候補はNによって動的に決定する。
# dp[i] を i 円引き出すのに最小の操作回数とする
# dp[i] = min_{j \in 引き出し額}(dp[i - j]) +1 なので更新できる

# 今回は実装の都合上集めるdpではなく配るdpで実装する


def full(shape, full_value):
    if isinstance(shape, tuple):
        sha = shape[::-1]
        ret = [full_value] * sha[0]
        for s in sha[1:]:
            ret = [ret.copy() for i in range(s)]
        return ret

        if len(shape) == 2:
            return [[full_value] * shape[1] for _ in range(shape[0])]
    else:
        return [full_value] * shape


INF = 10**9

N = int(input())
candi = [1]
i = 1
while 6 ** i <= N:
    candi.append(6**i)
    i += 1

i = 1
while 9 ** i <= N:
    candi.append(9**i)
    i += 1

candi.sort()

dp = full(N + 1, INF)
dp[0] = 0  # 初期化

for i in range(N):
    for j in candi:
        if i + j > N:
            continue
        dp[i + j] = min(dp[i + j], dp[i] + 1)

print(dp[-1])

Submission status: Accepted

Solution code:
n = int(input())
dp = [[False for _ in range(n + 5)] for __ in range(100)]
dp[0][0] = True

for i in range(100):
    for m in range(n):
        if dp[i][m] == True:
            for j in range(10):
                if m + 6 ** j > n: break
                dp[i + 1][m + 6 ** j] = True
            for j in range(10):
                if m + 9 ** j > n: break
                dp[i + 1][m + 9 ** j] = True
    if dp[i + 1][n]:
        print(i + 1)
        break

Submission status: Accepted

Solution code:
n = int(input())
dp = [10 ** 9] * (n + 5)
dp[0] = 0

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

Submission status: Accepted

Solution code:
n=int(input())
dp=[float("inf") for _ in range(n+1)]
dp[0]=0
for i in range(n):
    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:
import sys
from collections import defaultdict, deque
import bisect
from heapq import *
from math import factorial
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
# L = [list(input().strip())  for _ in range(N)]
# S = input().strip()

m = [
     1,
     6,
     6 ** 2,
     6 ** 3,
     6 ** 4,
     6 ** 5,
     6 ** 6,
     9,
     9 ** 2,
     9 ** 3,
     9 ** 4,
     9 ** 5,
]

dp = [[10 ** 18 for _ in range(N + 1)] for _ in range(len(m) + 1)]
dp[0][0] = 0

for i in range(1, len(m) + 1):
     for j in range(N + 1):
          dp[i][j] = dp[i - 1][j]

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

print(dp[len(m)][N])

Submission status: Accepted

Solution code:
N = int(input())


def fn(n, a):
    res = 0
    while n > 0:
        res += n % a
        n = n // a
    return res


ans = 1 << 60
for i in range(0, N+1):
    tmp = fn(i, 6) + fn(N - i, 9)
    ans = min(ans, tmp)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

    dp = [float('inf')] * (N+1)
    dp[0] = 0

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

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

    print(dp[-1])
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def chmin(a, b):
    if a < b:
        return (a)
    else:
        return (b)

ans = [100000000] * 100001
can = [1,6,9,36,81,216,729,1296,6561,7776, 46656, 59049]
ans[1] = 1
ans[6] = 1
ans[36] = 1
ans[216] = 1
ans[1296] = 1
ans[7776] = 1
ans[46656] = 1
ans[9] = 1
ans[81] = 1
ans[729] = 1
ans[6561] = 1
ans[59049] = 1

for i in range(2,100001):
    for j in can:
        if i > j:
            ans[i] = chmin(ans[i], ans[i-j]+1)

N = int(input())
print(ans[N])

Submission status: Accepted

Solution code:
n = int(input())

max6 = n//6

ans = 10**9

def count_func(m,k): #n:kを何回使うか、k:6or9
    if m<k:
        return m
    for i in range(1,8):
        if m<k**i:
            return count_func(m-k**(i-1),k)+1

    

for i in range(max6+1):
    ct6 = count_func(i,6)
    ct9 = count_func((n-6*i)//9,9)
    am = n-(i*6+((n-6*i)//9)*9)
    ans = min(ans,ct6+ct9+am)
    
print(ans)

Submission status: Accepted

Solution code:
import sys

n = int(sys.stdin.readline().rstrip())

def main():
    bit6 = [0] * 8
    bit9 = [0] * 7
    b = n
    for i in range(5, -1, -1):
        q, r = divmod(b, 9 ** i)
        bit9[i] = q
        b = r

    res = sum(bit6) + sum(bit9)

    for _ in range(n):
        i = 0
        while True:
            bit6[i] += 1
            if bit6[i] == 6:
                bit6[i] = 0
                i += 1
            else:
                break

        i = 0
        while True:
            bit9[i] -= 1
            if bit9[i] == -1:
                bit9[i] = 8
                i += 1
            else:
                break        

        res = min(res, sum(bit6) + sum(bit9))

    return res

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
import sys
from math import log, floor

n = int(sys.stdin.readline().rstrip())

def main():
    cand = set()
    for i in range(floor(log(n, 6)) + 1):
        if 6 ** i <= n:
            cand.add(6 ** i)
        if 9 ** i <= n:
            cand.add(9 ** i)
    cand = sorted(cand)

    res = set([0])
    cnt = 0
    while True:
        nex = set()
        for val in res:
            for c in cand:
                if val + c <= n:
                    nex.add(val + c)
                else:
                    break
        cnt += 1
        if n in nex:
            return cnt
        res = nex
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from itertools import product

def solve(N: int):
    nine = [9**i for i in range(5,0,-1)]
    six = [6**i for i in range(6,0,-1,)]
    answer = 10**6

    for six_bit in product([0,1,2,3,4,5],repeat = 6):
        tmp = 0
        for i in range(6):
            tmp += six[i]*six_bit[i]

        if tmp > N:
            continue
        
        count = sum(six_bit)
        cur = N-tmp
        for i in range(5):
            syou = cur//nine[i]
            cur%=nine[i]
            count += syou
        else:
            answer = min(answer,count+cur)
    print(answer)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())

ans = 100000

def sum_digits(n,m):
    r = 0
    while n:
        r, n = r + n % m, n // m
    return r
 
for i in range(N+1):
    ans = min(ans, sum_digits(i,6)+sum_digits(N-i,9))
 
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
def func(n,a):
    cnt=0
    while n!=0:
        r=n%a
        n=(n-r)//a
        cnt+=r
    return cnt

ans=N
for i in range(N+1):
    tmp=func(i,6)+func(N-i,9)
    ans=min(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
import heapq
N=int(input())
N_max=100000

d=set()
n=1
while n<=N_max:
    d.add(n)
    n*=6
n=1
while n<=N_max:
    d.add(n)
    n*=9

dp=[N_max+1 for _ in range(N_max+1)]
dp[0]=0
for i in range(1,N_max+1):
    for n in d:
        if i>=n:
            dp[i]=min(dp[i],dp[i-n]+1)

print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())
List9 = [9 ** i for i in range(1,7) if 9 ** i <= N]
List6 = [6 ** i for i in range(1,7) if 6 ** i <= N]

def recur(n,con):
  if n == 0:
    return con

  elif n < 6:
    return con + n
    
  elif n < 9:
    return con + (n - 5)

  else:
    max9 = [i for i in List9 if i <= n][-1]
    max6 = [i for i in List6 if i <= n][-1]
    
    return min(recur(n - max9,con + 1),recur(n - max6,con + 1))
    
print(recur(N,0))

Submission status: Accepted

Solution code:
N = int(input())

ans = N + 1
for t in range(N + 1):
    cnt = 0
    v6 = t
    while v6 > 0:
        cnt += v6 % 6
        v6 //= 6
    v9 = N - t
    while v9 > 0:
        cnt += v9 % 9
        v9 //= 9
    ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    dp = [n] * 200000
    dp[0] = 0
    
    for i in range(n):
        p6 = 1
        while True:
            if i + p6 > n:
                break
            dp[i + p6] = min(dp[i + p6], dp[i] + 1)
            p6 *= 6
        p9 = 1
        while True:
            if i + p9 > n:
                break
            dp[i + p9] = min(dp[i + p9], dp[i] + 1)
            p9 *= 9
    print(dp[n])


if __name__ == "__main__":
    main()

Submission status: Accepted

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

x = 6
while x <= n:
  for i in range(n-x+1):
    a[i+x] = min(a[i+x], a[i]+1)
  x *= 6

x = 9
while x <= n:
  for i in range(n-x+1):
    a[i+x] = min(a[i+x], a[i]+1)
  x *= 9

print(a[n])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
# 再帰的に求められる
memo = [-1] * 110000

# ベキ乗は英語でpower
def withdrawals(n):
    if n == 0:  # 最後まで下ろせたら完了である
        return 0
    if memo[n] != -1:  # すでに最適解がもとまっているならばその解を返す
        return memo[n]
    res = n  # すべて1円で支払ったと仮定する
    pow6 = 1
    while pow6 <= n:
        res = min(res, withdrawals(n - pow6) + 1)
        pow6 *= 6

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

    memo[n] = res
    return res


N = int(input())
withdrawals(N)
print(memo[N])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())

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

Submission status: Accepted

Solution code:
N=int(input())

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
memo = [-1] * 110000  # memo[i]がi円についての答え


def rec(n):
    if n == 0:
        return 0
    if memo[n] != -1:
        return memo[n]  # 探索済みならリターン

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

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


N = int(input())
rec(N)
print(memo[N])

Submission status: Accepted

Solution code:
import math
n = int(input())
dp = [float("inf")] * (10 ** 5 + 10)
dp[0] = 0
for i in range(1,n + 1):
  power = 1
  while n >= power:
    dp[i] = min(dp[i],dp[i - power] + 1)
    power *= 6
  power = 1
  while n >= power:
    dp[i] = min(dp[i],dp[i - power] + 1)
    power *= 9
print(dp[n])

Submission status: Accepted

Solution code:
N = int(input())
#N=44852
LIST=[10**9]*(10**7)
LIST[0]=1

i=1
c=1
while(6**i <= N):
    LIST[c]=6**i
    c+=1
    if(9**i <= N):
        LIST[c]=9**i
        c+=1
    i+=1
LIST=LIST[0:c]
LIST=list(sorted(LIST,reverse=True))
MIN=10**10

def calc(L,i,c):
    global MIN
    global N
    if(MIN<c):
        return
    if(N-L >= LIST[i]):
        calc(L+LIST[i],i,c+1)
        if(MIN<c):
            return
    if(len(LIST)-2>=i):
        calc(L,i+1,c)
        if(MIN<c):
            return
    if(N==L):
        MIN=min(MIN,c)
  

calc(0,0,0)
print(MIN)

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()

# dp[i] := i円引き出すのに必要な最小回数
dp = [INF] * (N+1)
dp[0] = 0
for i in range(N):
    # 3種類の引き出し方に対応する遷移をする
    dp[i+1] = min(dp[i+1], dp[i] + 1)
    j = 6
    while i+j <= N:
        dp[i+j] = min(dp[i+j], dp[i] + 1)
        j *= 6
    j = 9
    while i+j <= N:
        dp[i+j] = min(dp[i+j], dp[i] + 1)
        j *= 9
print(dp[N])

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()

# dp[i] := i円引き出すのに必要な最小回数
dp = [INF] * (N+1)
dp[0] = 0
for i in range(N):
    # 3種類の引き出し方に対応する遷移をする
    dp[i+1] = min(dp[i+1], dp[i] + 1)
    j = 1
    while i+6**j <= N:
        dp[i+6**j] = min(dp[i+6**j], dp[i] + 1)
        j += 1
    j = 1
    while i+9**j <= N:
        dp[i+9**j] = min(dp[i+9**j], dp[i] + 1)
        j += 1
print(dp[N])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())

coin_list = [1]

i=1
while 6**i <= 10**5:
    coin_list.append(6**i)
    i+=1

i=1
while 9**i <= 10**5:
    coin_list.append(9**i)
    i+=1

#j番目までのコインでi円を作る時の最小回数#jは0始まり
dp = [[10**5 for i in range(n+1)] for j in range(len(coin_list))]
dp[0] = [i for i in range(n+1)]

for i in range(n+1):
    for j,coin in enumerate(coin_list):
        if j==0:
            continue
        if coin <= i:
            dp[j][i] = min(dp[j-1][i],dp[j][i-coin]+1)
        else:
            dp[j][i] = dp[j-1][i]
print(dp[-1][n])

Submission status: Accepted

Solution code:
import sys, math

def input():
    return sys.stdin.readline()[:-1]

def main():
    N = int(input())
    D = [k for k in range(N+1)]
    for d in range(10):
        for k in range(N-6**d+1):
            D[k+6**d] = min(D[k+6**d],D[k]+1)
    for d in range(10):
        for k in range(N-9**d+1):
            D[k+9**d] = min(D[k+9**d],D[k]+1)
    print(D[N])
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

dp = [float("inf")] * (n + 1)

dp[0] = 0

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

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

print(dp[n])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
dp = [1000000] * 100010
dp[0] = 0
for i in range(n):
    a = 1
    while i + a <= 100000:
        dp[i + a] = min(dp[i + a], dp[i] + 1)
        a *= 6
    b = 1
    while i + b <= 100000:
        dp[i + b] = min(dp[i + b], dp[i] + 1)
        b *= 9
print(dp[n])

Submission status: Accepted

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

i6 = 1
while 6**i6 <=N:
  ps.append(6**i6)
  i6 += 1

i9 = 1
while 9**i9 <=N:
  ps.append(9**i9)
  i9 += 1

len_ps = len(ps)
dp = [float('inf') for _ in range(N+1)]
dp[0] = 0
for i in range(1,N+1):
  for j in range(len_ps):
    if i-ps[j]>=0:dp[i] = min(dp[i], 1+dp[i-ps[j]])

print(dp[-1])

Submission status: Accepted

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

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

        
print(dp[n])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
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 = [0] * (N+1)

for i in range(1,N+1):
    temp = []
    for c in coin:
        if i - c >= 0:
            temp.append(dp[i-c] + 1)
    dp[i] = min(temp)
print(dp[-1])

Submission status: Accepted

Solution code:
n = int(input())
def calc(c, p):
    res = 0
    while c:
        res += c % p
        c = c // p
    return res
ans = n
for i in range(n+1):
    cand = calc(i, 6) + calc(n - i, 9)
    ans = min(ans, cand)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
ans=10**5

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

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
li6=[46656,7776,1296,216,36,6,1]
li9=[59049,6561,729,81,9,1]
dp6=[0]*(n+1)
dp9=[0]*(n+1)
dp6[1]=1
dp9[1]=1
ans=[]
for i in range(2,n+1):
    for j in range(7):
        if i>=li6[j]:
            k=i-li6[j]
            break
    dp6[i]=1+dp6[k] 
for i in range(2,n+1):
    for j in range(6):
        if i>=li9[j]:
            k=i-li9[j]
            break
    dp9[i]=1+dp9[k]  
for i in range(n+1):
    ans.append(dp6[i]+dp9[n-i])                    
print(min(ans))

Submission status: Accepted

Solution code:
n=int(input())
import math
ansa=[0]
ansb=[0]
ans=[]
cnt=0
x=0
y=0
for i in range(1,n+1):
    while 9**(x+1)<=i:
        x+=1
    for j in range(x,-1,-1):
        z=(math.floor(i/(9**j))%9)
        i-=(9**j)*z
        cnt+=z
    ansa.append(cnt)
    cnt=0    
    
for i in range(1,n+1):
    while 6**(y+1)<=i:
        y+=1
    for j in range(y,-1,-1):
        z=(math.floor(i/(6**j))%6)
        i-=(6**j)*z
        cnt+=z
    ansb.append(cnt)
    cnt=0
    
for i in range(n+1):
    ans.append(ansa[i]+ansb[n-i])
    
print(min(ans))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin
import bisect

n = int(stdin.readline().rstrip())
roku = [0]+[6**_ for _ in range(10) if 6**_ <= n]
kyu = [0]+[9**_ for _ in range(10) if 9**_ <= n]

ma = 10**10
for i in range(n+1):
    six = i
    nine = n-i
    count = 0
    while True:
        if six == 0:
            break
        six -= roku[bisect.bisect(roku,six)-1]
        count += 1
    while True:
        if nine <= 0:
            break
        nine -= kyu[bisect.bisect(kyu,nine)-1]
        count += 1
    ma = min(ma,count)
print(ma)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
from math import floor
N = int(input())
res = N
for i in range(N+1):
    cc = 0
    t = i
    while t > 0:
        cc += t % 6
        t = t // 6
    t = N - i
    while t > 0:
        cc += t % 9
        t = t // 9
    if res > cc:
        res = cc
print(floor(res))

Submission status: Accepted

Solution code:
N = int(input())
INF = float('inf')
dp = [INF for _ in range(N+1)]
dp[0] = 0

for n in range(N + 1):
    power = 0
    while pow(6, power) <= n:
        dp[n] = min(dp[n], dp[n - pow(6, power)] + 1)
        power += 1

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

print(dp[N])

Submission status: Accepted

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

for n in range(N + 1):
    power = 0
    while pow(6, power) <= n:
        dp[n] = min(dp[n], dp[n - pow(6, power)] + 1)
        power += 1

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

print(dp[N])

Submission status: Accepted

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

for n in range(N + 1):
    power = 0
    while pow(6, power) <= N:
        dp[n] = min(dp[n], dp[n - pow(6, power)] + 1)
        power += 1

    power = 0
    while pow(9, power) <= N:
        dp[n] = min(dp[n], dp[n - pow(9, power)] + 1)
        power += 1

print(dp[N])

Submission status: Accepted

Solution code:
def main():
    weight = [6**i for i in range(7)] + [9**i for i in range(1, 6)]
    W = int(input())
    n = len(weight)

    dp = [[1 << 62 for i in range(W + 1)] for j in range(n + 1)]
    for i in range(n):
        dp[i][0] = 0
    for i in range(n):
        for w in range(W + 1):
            if w - weight[i] >= 0:
                dp[i + 1][w] = min(dp[i][w], dp[i+1][w - weight[i]] + 1)
            else:
                dp[i + 1][w] = dp[i][w]

    print(dp[n][W])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

ans = n
for k in range(0,n+1):
    count = 0
    for i in range(0,7):
        num6 = k//(6**i)%6
        count += num6

    for i in range(0,6):
        num9 = (n-k)//(9**i)%9
        count += num9

    if count < ans: 
        ans = count

print(ans)

Submission status: Accepted

Solution code:
def c6(x):
    res=0
    while x>0:
        res,x=res+x%6,x//6
    return res

def c9(y):
    res=0
    while y>0:
        res,y=res+y%9,y//9
    return res

N=int(input())
ans=100000
for x in range(N+1):
    # print(x,N-x,c6(x),c9(N-x),c6(x)+c9(N-x))
    ans=min(ans,c6(x)+c9(N-x))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

s = 6
m = 9
Can = [1]
count = 2
while s < 10**5:
    Can.append(s)
    s = 6**count
    count += 1

count = 2
while m < 10**5:
    Can.append(m)
    m = 9**count
    count += 1

DP = [1]
for i in range(1,n):
    dp_can = []
    if i+1 in Can:
        # print(i+1)
        DP.append(1)
        continue
    
    for num in Can:
        if num > i:
            continue
        dp_can.append(DP[i-num]+1)
    DP.append(min(dp_can))

# print(DP)
print(DP[-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
count=N
for i in range(0,N+1,1):
    n=(i%9 + (N-i)%6)

    n9=0
    num9=i//9
    while num9:
        n9+=num9%9
        num9//=9

    n6=0
    num6=(N-i)//6
    while num6:
        n6+=num6%6
        num6//=6
    count=min(n9+n6+n,count)
print(count)

Submission status: Accepted

Solution code:
#morau dp
N=int(input())
dp=[float('inf') for i in range((10**5)*2)]
L6=[6**i for i in range(1,8)]#7ko
L9=[9**i for i in range(1,7)]#6ko
a=[1]
L=a+L6+L9
L.sort()#14ko
dp[0]=0
for i in range(N+1):
    for j in range(14):
        if i-L[j]>=0:
            dp[i]=min(dp[i],1+dp[i-L[j]])
print(dp[N])

Submission status: Accepted

Solution code:
#kubaru dp
N=int(input())
dp=[float('inf') for i in range((10**5)*2)]
L6=[6**i for i in range(1,8)]#7ko
L9=[9**i for i in range(1,7)]#6ko
a=[1]
L=a+L6+L9
L.sort()#14ko
dp[0]=0
for i in range(N+1):
    for j in range(14):
        if i+L[j]<=N:
            dp[i+L[j]]=min(dp[i+L[j]], dp[i]+1)
print(dp[N])

Submission status: Accepted

Solution code:

if __name__ == '__main__':
    N=int(input())

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


    print(dp[N])

Submission status: Accepted

Solution code:
N=int(input())
ans=[0, 1, 2, 3, 4, 5]+[100001]*(N-5)
  
for i in range(N):
  for j in range(1, 7):
    if i+6**j<=N:
      ans[i+6**j]=min(ans[i]+1, ans[i+6**j])
      
  for j in range(1, 6):
    if i+9**j<=N:
      ans[i+9**j]=min(ans[i]+1, ans[i+9**j])
      
print(ans[N])

Submission status: Accepted

Solution code:
import math
n=int(input())
#c=0
#ただのDPやんけ
#0~N
dp=[100000000000000]*(n+1)
dp[0]=0
for i in range(1,min(6,n+1)):
    dp[i]=i
#print(dp)
for i in range(n+1):
    for j in range(1,7):
        if i+6**j<=n:
            dp[i+6**j]=min(dp[i+6**j],dp[i]+1)
    for j in range(1,6):
        if i+9**j<=n:
            dp[i+9**j]=min(dp[i+9**j],dp[i]+1)

print(dp[n])

Submission status: Accepted

Solution code:
N = int(input())

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

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

print(dp[N])

Submission status: Accepted

Solution code:
N=int(input())
dstb=[1]+[6**i for i in range(1,7)]+[9**j for j in range(1,6)]
DP=[10**5]*(10**5*2)
DP[0]=0
for i in range(N+1):
  for j in dstb:
    DP[i+j]=min(DP[i+j], DP[i]+1)

print(DP[N])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect, functools, copy
# import resource
# print(resource.getrlimit(resource.RLIMIT_STACK))

# resource.setrlimit(resource.RLIMIT_STACK, (8388608, 67104768))
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
# print(sys.getrecursionlimit())
sys.setrecursionlimit(10**7)
# print(sys.getrecursionlimit())
inf = float('inf')
mod = 10**9+7
ans = inf ; count = 0; pro = 1

n=int(input())
count=0
# memo=[0]*(n+1)
# memo[0]=0
@functools.lru_cache(maxsize=None)
def func(n):
    if n==0:return 0
    # if memo[n] or n==0:return memo[n]
    # print(n)
    # global count
    # count+=1
    # if count%10==0:print(count)
    if n==0:
        return 0
    re=inf
    k=s=1
    while 9**s<=n:
        re=min(re,func(n-9**s)+1)
        s+=1
    while 6**k<=n:
        re=min(re,func(n-6**k)+1)
        k+=1
    re=min(re,func(n-1)+1)
    # memo[n]=re
    return re
    
print(func(n))
# print(memo)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect, functools, copy
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**7)
inf = float('inf')
mod = 10**9+7
ans = inf ; count = 0; pro = 1

n=int(input())
count=0
# @functools.lru_cache(maxsize=None)
memo=[0]*(n+1)
memo[0]=0
def func(n):
    if memo[n] or n==0:return memo[n]
    # print(n)
    # global count
    # count+=1
    # if count%10==0:print(count)
    if n==0:
        return 0
    re=func(n-1)+1
    k=s=1
    while 9**s<=n:
        re=min(re,func(n-9**s)+1)
        s+=1
    while 6**k<=n:
        re=min(re,func(n-6**k)+1)
        k+=1
    re=min(re,func(n-1)+1)
    memo[n]=re
    return re
    
print(func(n))
# print(memo)