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())

answer = N
for i in range(N+1):
    count = 0
    t = i
    # i円を6円で払い、残りを9円で払う
    while t:
        count += t%6
        t //= 6
    t = N-i
    while t:
        count += t%9
        t //= 9
    answer = min(answer, count)
print(answer)

Submission status: Accepted

Solution code:
N = int(input())

list_6_9 = [1]

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

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


cnt_draw_list = [100000] * (N+1)
cnt_draw_list[0] = 0


## ループして引き落とし回数を更新していく
for n in range(1,N+1):
  for draw_cash in list_6_9:
    tmp = n - draw_cash
    if tmp >= 0:
      cnt_draw_list[n] = min(cnt_draw_list[n],cnt_draw_list[tmp] + 1)


print(cnt_draw_list[N])

Submission status: Accepted

Solution code:
import sys
from collections import deque
from functools import reduce
import copy
import math


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(inputs):
    n = int(inputs[0])
    LIMIT = 100000
    sixs = [6]
    nines = [9]
    while sixs[-1] <= LIMIT:
        sixs.append(6 * sixs[-1])
    sixs.pop()
    while nines[-1] <= LIMIT:
        nines.append(9 * nines[-1])
    nines.pop()

    choises = [1]
    choises.extend(sixs)
    choises.extend(nines)

    # [count]
    dp = [0]

    for i in range(1, n+1):
        candidates = []
        for c in choises:
            if i - c >= 0:
                candidates.append(dp[i-c] + 1)
        dp.append(min(candidates))

    return dp[-1]


def string_to_int(string):
    return list(map(int, string.split()))


if __name__ == "__main__":
    ret = solve(inputs(1))
    print(ret)

Submission status: Accepted

Solution code:
N = int(input())

dp = [0]*(N+10)

for n in range(1, N+1):
  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])

Submission status: Accepted

Solution code:
# 貰うDP
INF = float('inf')
n = int(input())
a = [1]
i = 6
while i <= n:
  a.append(i)
  i *= 6
i = 9
while i <= n:
  a.append(i)
  i *= 9
t = [0] * (n + 1)
for i in range(1, n + 1):
  k = INF
  for j in a:
    if i - j >= 0 and k > t[i - j] + 1:
      k = t[i - j] + 1
  t[i] = k
print(t[n])

Submission status: Accepted

Solution code:
import queue
N = int(input())
M = [-1]*(N+1)
M[0] = 0
q = queue.Queue()
q.put(0)
while not(q.empty()):
  c = q.get()
  i = M[c]
  for n in range(1, 20):
    s = c+6**n
    if s <= N and (M[s] < 0 or i+1 < M[s]):
      M[s] = i+1
      q.put(s)
  for n in range(1, 20):
    s = c+9**n
    if s <= N and (M[s] < 0 or i+1 < M[s]):
      M[s] = i+1
      q.put(s)
#print(M)
for i in reversed(range(0, N+1)):
  if not(M[i] < 0):
    r = M[i]+(N-i)
    break
print(r)

Submission status: Accepted

Solution code:
n = int(input())
dp = [float('inf')]*(n+1)
dp[0] = 0
for i in range(n+1):
    power = 1
    #6の階乗
    while power <= i:
        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())
ans=N
for i in range(N+1):
    element_cnt=0
    t=i
    '''Nを6の累乗で処理する部分(i)と9の累乗で処理する部分(j)に分ける
    ある数(i)を6で割った余りは6のゼロ乗の要素がいくつ含まれるかを示す
    ある数の6の商をさらに6で割った余りは、ある数に6の1乗がいくつ含まれるかを示す
    ある数の6の商の6の商をさらに6で割った余りは、ある数に6の2乗がいくつ含まれるかを示す
    したがって、ある数を6で割って余りと商を順に処理すれば6の累乗の要素がどれだけあるかがわかる。
    最終的に商がゼロになるまで繰り返す
    '''
    while t>0:
        element_cnt+=t%6
        t//=6
    j=N-i
    while j>0:
        element_cnt+=j%9
        j//=9
    ans = min(ans,element_cnt)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

#引き出せる金額の列挙
Withdr = [1] + [6**i for i in range(1, 7)] + [9**i for i in range(1,6)]
INF = 100010
dp = [INF]*159050
dp[0] = 0

#全てを順に計算
for j in range(n + 1):
    #あるnに対し複数の計算方法があるため、それらの中で一番少ないものをdpに格納する
    for WithdrOrder in Withdr:
        #dp[j + WithdrOrder]は今までに計算した最小値とdp[j]から1回で引き出せる金額を足したものとの比較で算出
        dp[j + WithdrOrder] = min(dp[j + WithdrOrder], dp[j] + 1)
print(dp[n])

Submission status: Accepted

Solution code:
import sys
from collections import deque
from collections import  Counter
import statistics
import math

stdin = sys.stdin

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

n = ni()

dp = [99999999]*(n+1)
dp[0] = 0
for i in range(1, n+1):
    dp[i] = dp[i-1] + 1
    k = 6
    while i-k >= 0:
        dp[i] = min(dp[i], dp[i-k]+1)
        k *= 6
    k = 9
    while i-k >= 0:
        dp[i] = min(dp[i], dp[i-k]+1)
        k *= 9
print(dp[n])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

INF = 1000000

N = int(input())
m = [INF] * 100001
m[0] = 0
m[1] = 1

def f(N):
    if m[N] != INF:
        return m[N]

    tmp = INF

    tmp = min(f(N - 1) + 1, tmp)

    a = 6
    while a <= N:
        tmp = min(f(N - a) + 1, tmp)
        a *= 6

    a = 9
    while a <= N:
        tmp = min(f(N - a) + 1, tmp)
        a *= 9

    m[N] = tmp
    return tmp

print(f(N))

Submission status: Accepted

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

for i in range(N+1):
    count = 0
    t = i
    while(t):
        count += t%6
        t//=6
    t = N-i
    while(t):
        count += t%9
        t//=9
    score = min(count,score)

print(score)

Submission status: Accepted

Solution code:
def nsin(X,n):
    if(int(X/n)):
        return nsin(int(X/n),n)+str(X%n)
    return str(X)

N = int(input())
score = N
for i in range(N+1):
    score = min(score,sum(map(int,nsin(i,6)+nsin(N-i,9))))
print(score)

Submission status: Accepted

Solution code:
# 動的計画法(dp)
# dp[N](数列)を求めたい。
# dp[0]からdp[N-1]は既知(最小となるっている)とする。
# dp[N] = (dp[N-1] + 1) , (dp[N-6] + 1) , ... , (dp[N-6^i] + 1) , (dp[N-9] + 1) , ... , (dp[N-9^j] + 1)の中から最小のものを選べば良い
# プログラム上では0からNまで回して1つずつ最小化すれば良い
N = int(input())

INF = 10**7
dp = [INF for _ in range(N+1)] # 0からNまで
dp[0] = 0 # 0番目以外は大きい値に初期化

for i in range(1, N+1):
    dp[i] = dp[i-1] + 1
    power = 6
    while power <= N: # N-6^xが非負の範囲で
        dp[i] = min(dp[i], dp[i - power] + 1)
        power *= 6
    power = 9
    while power <= N: # N-9^xが非負の範囲で
        dp[i] = min(dp[i], dp[i - power] + 1)
        power *= 9

print(dp[N])


"""
# 大きい方から貪欲に取るのは誤り(例えば12について、12=9+1+1+1になるが12=6+6の方がより少ない)
N = int(input())

money = [1]
for i in range(1, 100):
    if 6**i <= N:
        money.append(6**i)
    if 9**i <= N:
        money.append(9**i)
    if 6**i > N and 9**i > N:
        break
money.sort()
money.reverse()

zannkinn = N
ans = 0
for i in range(len(money)):
    ans += zannkinn//money[i]
    zannkinn = zannkinn % money[i]
    if zannkinn == 0:
        break

print(ans)
"""

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
from itertools import permutations,groupby
import sys
import bisect
import string
alp=string.ascii_lowercase
sys.setrecursionlimit(10**6)
def SI():
    return input().split()
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
mo=10**9+7
#mo=998244353
#input=sys.stdin.readline

n=I()
p6=[6**i for i in range(0,7)][::-1]
p9=[9**i for i in range(0,7)][::-1]
ans=n

for i in range(n+1):
    m=0
    n6=i
    n9=n-i
    for j in p6:
        m+=n6//j
        n6%=j
    for j in p9:
        m+=n9//j
        n9%=j
    ans=min(ans,m)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = [1] + [6 ** i for i in range(1, 7)] + [9 ** i for i in range(1, 6)]

INF = 10 ** 5
dp = [INF] * 200000
dp[0] = 0

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

print(dp[n])

Submission status: Accepted

Solution code:
N = int(input())
dp = [0] * (N + 1)
for i in range(1, N + 1):
    cnt = i
    for j in range(1, 7):
        q = 6 ** j
        if i >= q:
            cnt = min(cnt, dp[i - q] + 1)
    for j in range(1, 6):
        q = 9 ** j
        if i >= q:
            cnt = min(cnt, dp[i - q] + 1)
    dp[i] = cnt
print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())
dp = list(range(N + 1))

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

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

print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())
dp = [float("inf") for i in range(N+100)]
dp[0] = 0 
for i in range(1,N+50):
    r = 1 
    dp[i] = min(dp[i],dp[i-r]+1)
    p = 6 
    while (i>=p) :
        dp[i] = min(dp[i],dp[i-p]+1)
        p *= 6
    q = 9 
    while (i>=q) :
        dp[i] = min(dp[i],dp[i-q]+1)
        q *= 9
print(dp[N])

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())
ans = n
for i in range(n+1):
    cont=0
    j = n-i
    while i>0:
        cont+=i%6
        i//=6
    while j>0:
        cont+=j%9
        j//=9
    ans=min(ans,cont)
print(ans)

Submission status: Accepted

Solution code:
# 貰うDP
N = int(input())

INF = 10 ** 5 + 1

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

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

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

print(dp[N])

Submission status: Accepted

Solution code:
# 配るDP
N = int(input())

INF = 10 ** 5 + 1

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

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

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

print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())

INF = 10 ** 5 + 1

dp = [0 for _ in range(INF)]

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

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

print(dp[N])

Submission status: Accepted

Solution code:
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

N = I()

val = [1]
temp = 1
while 1:
    temp *= 6
    if temp<=10**5:
        val.append(temp)
    else:
        break

temp = 1
while 1:
    temp *= 9
    if temp<=10**5:
        val.append(temp)
    else:
        break

val.sort(reverse=True)

def rec(price,i):
    if i==len(val)-1:
        return price
    else:
        q,m = divmod(price,val[i])
        if m==0:
            return q
        else:
            if q>=9:
                return float('inf')
            else:
                x = []
                for j in range(q+1):
                    x.append(rec(price-j*val[i],i+1) + j)
                return min(x)

print(rec(N,0))

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:
# -*- coding: utf-8 -*-

N = int(input())

ans = N
for i in range(N // 9 + 1):
    nine = i * 9
    six = N - nine
    tmp_ans = 0
    while nine > 0:
        tmp_ans += nine % 9
        nine = nine // 9
    while six > 0:
        tmp_ans += six % 6
        six = six // 6
    ans = min(tmp_ans, ans)

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
ans=10**100
for t in range(n+1):
    p=t
    q=n-p
    c=0
    while p>0:
        c+=p%6
        p=p//6
    while q>0:
        c+=q%9
        q=q//9
    ans=min(ans,c)
print(ans)

Submission status: Accepted

Solution code:
#計算量解析
#O(NlogN)
class Method1:
  def __init__(self, N):
    self.N = N
    self.memo = [-1] * 110000
  
  def rec(self,n):
    if n == 0:
      return 0
    if self.memo[n] != -1:
      return self.memo[n]
    res = n
    cnt = 0
    while 6 ** cnt <= n:
      res = min(res, self.rec(n - 6 ** cnt) + 1)
      cnt += 1
    cnt = 0
    while 9 ** cnt <= n:
      res = min(res, self.rec(n - 9 ** cnt) + 1)
      cnt += 1
    self.memo[n] = res
    return res

  def ans(self,):
    print(self.rec(self.N))
    
#配るDP   
class Method2():
  def __init__(self, N):
    self.N = N
    self.dp = [N] * 110000
  def ans(self, ):
    self.dp[0] = 0
    for n in range(1,self.N + 1):
      cnt = 0
      while 6 ** cnt <= n:
        self.dp[n] = min(self.dp[n], self.dp[n - 6 ** cnt] + 1)
        cnt += 1
      cnt = 0
      while 9 ** cnt <= n:
        self.dp[n] = min(self.dp[n], self.dp[n - 9 ** cnt] + 1)
        cnt += 1
    print(self.dp[self.N])

#
class Method3():
  def __init__(self, N):
    self.N = N
    self.dp = [N] * 110000
    
if __name__ == '__main__':
  inputN = int(input())
  #method = Method1(inputN)
  method = Method2(inputN)
  method.ans()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    dp = [float('inf') for _ in range(N+1)]
    dp[0] = 0
    cand = [1]
    p = 6
    while p <= N:
        cand.append(p)
        p *= 6
    p = 9
    while p <= N:
        cand.append(p)
        p *= 9

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


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

Submission status: Accepted

Solution code:
# 貰うDP
n = int(input())
a = [1]
i = 6
while i <= n:
  a.append(i)
  i *= 6
i = 9
while i <= n:
  a.append(i)
  i *= 9
t = [0] * (n + 1)
for i in range(1, n + 1):
  k = float("inf")
  for j in a:
    if i - j >= 0 and k > t[i - j] + 1:
      k = t[i - j] + 1
  t[i] = k
print(t[n])

Submission status: Accepted

Solution code:
# 貰うDP
n = int(input())
a = [1]
i = 6
while i <= n:
  a.append(i)
  i *= 6
i = 9
while i <= n:
  a.append(i)
  i *= 9
t = [float("inf")] * (n + 1)
t[0] = 0
for i in range(1, n + 1):
  k = float("inf")
  for j in a:
    if i - j >= 0 and k > t[i - j] + 1:
      k = t[i - j] + 1
  t[i] = k
print(t[n])

Submission status: Accepted

Solution code:
n = int(input())
a = [1]
i = 6
while i <= n:
  a.append(i)
  i *= 6
i = 9
while i <= n:
  a.append(i)
  i *= 9
t = [float("inf")] * (n + 1)
t[0] = 0
for i in range(n):
  for j in a:
    if i + j <= n and t[i + j] > t[i] + 1:
      t[i + j] = t[i] + 1
print(t[n])

Submission status: Accepted

Solution code:
N = int(input())

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

arr = [1,6,9]

for i in range(len(arr)):
    oriArrVal = arr[i]
    val = arr[i]
    while val <= N:
        index = val
        while index <= N:
            dp[index] = min(dp[index],dp[index - val]+1)
            index += 1
            # print(index)
        if oriArrVal == 1:
            val += index
        else : val *= oriArrVal

print(dp[N])

Submission status: Accepted

Solution code:
def resolve():
    N=int(input())
    mini=10**10
    for i in range(N+1):
        j=N-i
        mini=min(mini,f(i,6)+f(j,9))
    print(mini)


def f(n,m):#nをm進数にしたときの桁和
    i=0
    while n>0:
        i=i+n%m
        n=n//m
    return(i)
resolve()

Submission status: Accepted

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

n = int(input())

dp = [0] * (n+1)

for i in range(0, n+1):
  dp[i] = i
  six = 6
  nine = 9
  while True:
    if i - six >= 0:
      dp[i] = min(dp[i], dp[i-int(six)]+1)
      six *= 6
    else:
      break
  while True:
    if i - nine >= 0:
      dp[i] = min(dp[i], dp[i-int(nine)]+1)
      nine*= 9
    else:
      break
#print(*dp)
print(dp[-1])

Submission status: Accepted

Solution code:
N = int(input())

# def make_array(shape, defval=0, dtype=int):
#     res = np.zeros(shape, dtype)
#     res[:] = defval
#     return res.tolist()


# memo = make_array((15, N + 1), N * 2)
memo = [[N * 2] * (N + 1) for _ in range(15)]
memo[0][0] = 0

values = []

i = 1
while i <= N:
    values.append(i)
    i *= 6
i = 9
while i <= N:
    values.append(i)
    i *= 9

for i in range(len(values)):
    v = values[i]
    for w in range(N + 1):
        if v > w:
            memo[i + 1][w] = memo[i][w]
        else:
            memo[i + 1][w] = min(memo[i][w], memo[i + 1][w - v] + 1)
print(memo[len(values)][N])

Submission status: Accepted

Solution code:
import numpy  as np

N = int(input())


def make_array(shape, defval=0, dtype=int):
    res = np.zeros(shape, dtype)
    res[:] = defval
    return res.tolist()


memo = make_array((15, N + 1), N * 2)
memo[0][0] = 0

values = []

i = 1
while i <= N:
    values.append(i)
    i *= 6
i = 9
while i <= N:
    values.append(i)
    i *= 9

for i in range(len(values)):
    v = values[i]
    for w in range(N + 1):
        if v > w:
            memo[i + 1][w] = memo[i][w]
        else:
            memo[i + 1][w] = min(memo[i][w], memo[i + 1][w - v] + 1)
print(memo[len(values)][N])

Submission status: Accepted

Solution code:
import numpy  as np

N = int(input())

# log_6 10^5 < 7
# log_9 10^5 < 6
# 15 = 1 + 6 + 5
memo = np.zeros((15, N + 1),int)
memo[:, :] = N * 2
memo = memo.tolist()
memo[0][0] = 0

values = []

i = 1
while i <= N:
    values.append(i)
    i *= 6
i = 9
while i <= N:
    values.append(i)
    i *= 9

for i in range(len(values)):
    v = values[i]
    for w in range(N+1):
        if v > w:
            memo[i + 1][w] = memo[i][w]
        else:
            memo[i + 1][w] = min(memo[i][w], memo[i+1][w - v] + 1)
print(int(memo[len(values)][N]))

Submission status: Accepted

Solution code:
n=int(input())
dp=list(range(110000))
for i in range(n+1):
    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:
n = int(input())
memo = [-1] * (n+1)
import sys
sys.setrecursionlimit(1000000)
def f(n):
    if n == 0:
        return 0
    if memo[n] != -1:
        return memo[n]
    res = n
    pow6 = 1
    pow9 = 1
    res = min(res, f(n - 1) + 1)
    while pow6*6 <= n:
        pow6 *= 6
        res = min(res, f(n - pow6) + 1)
        
    while pow9*9 <= n:
        pow9 *= 9
        res = min(res, f(n - pow9) + 1)
        
    memo[n] = res
    return res
print(f(n))

Submission status: Accepted

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

Submission status: Accepted

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

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

for i in range(N+1):
    #iの分だけ6**xで構成
    cnt = 0
    a = i
    b = N-i
    while a > 0:
        idx = bisect.bisect_right(sixs, a)
        cnt += a // sixs[idx-1]
        a -= (a // sixs[idx-1]) * sixs[idx-1]

    while b > 0:
        idx = bisect.bisect_right(nines, b)
        cnt += b // nines[idx-1]
        b -= (b // nines[idx-1]) * nines[idx-1]

    ans = min(ans, cnt)

print(ans)

Submission status: Accepted

Solution code:
n=int(input())

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

#初期値：n回（n円は1円をn回引き出すことでも得られる）
dp=list(range(n+1))

for item in l:
  for i in range(item,n+1):
    #よりよい引き出し方に変えていく
    dp[i]=min(dp[i-item]+1, dp[i])

print(dp[-1])

Submission status: Accepted

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


def get_all_values(N, v):
    all_values = []

    current = v
    while current <= N:
        all_values.append(current)
        current *= v

    return all_values


def get_min_number(memo, all_values, N):
    if N in memo:
        return memo[N]

    if N in all_values:
        return 1
    elif N < 6:
        return N
    else:
        min_number = min(
            [get_min_number(memo, all_values, N - v) + 1 for v in all_values if N - v > 0]
        )
        memo[N] = min_number
        return min_number


def solve(N):
    # Get all values and sort in descent order
    all_values = [1] + get_all_values(N, 6) + get_all_values(N, 9)
    sorted_all_values = list(reversed(sorted(all_values)))

    # Recursively get minimum number
    memo = {}
    ans = get_min_number(memo, sorted_all_values, N)

    return ans


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

    # Solve
    ans = solve(N)

    # Answer
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
y=int(input())

res=[]

for i in range(1,y+1):
	cnt=0
	y1=i
	y2=y-i

	for j in range(6,0,-1):
		t9=9**j
		if y1>=t9:
			cnt+=y1//t9
			y1=y1%t9
	y2+=y1

	for j in range(7,0,-1):
		t6=6**j
		if y2>=t6:
			cnt+=y2//t6
			y2=y2%t6

	cnt+=y2
	res.append(cnt)

print(min(res))

Submission status: Accepted

Solution code:
import bisect as bi
N = int(input())
li6 = [6 ** i for i in range(7)]
li9 = [9 ** j for j in range(6)]

def s69(n):
  if n < 6:
    return n
  else:
    s6 = li6[bi.bisect(li6, n)-1]
    s9 = li9[bi.bisect(li9, n)-1]
    return min(n // s6 + s69(n % s6), 1 + s69(n-s9))
print (s69(N))

Submission status: Accepted

Solution code:
N = int(input())
ans = N
for n9 in range(N//9+1):
    a = N - 9*n9
    if a < 0:
        continue
    c = 0
    while a >= 6:
        c += a % 6
        a = a // 6
    c2 = 0
    while n9 >= 9:
        c2 += n9 % 9
        n9 = n9 // 9
    cost = a + c + c2 + n9
    ans = min(ans, cost)
print(ans)

Submission status: Accepted

Solution code:
import math
from collections import deque

n = int(input())

log_six = math.floor(math.log(n, 6))
log_nine = math.floor(math.log(n, 6))

count = [-1]*(n*100)
count[0] = 0
todo = deque([0])

while todo:
    i = todo.popleft()

    for j in range(1, log_six+1):
        money = i + 6 ** j

        if money <= n and count[money] is -1:
            count[money] = count[i] + 1
            todo.append(money)

    for k in range(1, log_nine+1):
        money = i + 9 ** k

        if money <= n and count[money] is -1:
            count[money] = count[i] + 1
            todo.append(money)

    if count[i+1] is -1:
        count[i+1] = count[i] + 1
        todo.append(i+1)

    if count[n] != -1:
        break

print(count[n])

Submission status: Accepted

Solution code:
N = int(input())

A = []

for i in range(1, 10):
    A.append(6 ** i)
    A.append(9 ** i)
    A.append(1)

B = [x for x in A if x < 1000000 ]


dp = [0] * (N + 1)
for i in range(N+1):
    if i == 0:
        dp[0] = 0
    else:
        tmp = 10 ** 10
        for j in B:
            if i >= j :
                tmp = min(tmp, dp[i-j]+1)
        dp[i] = tmp

print(dp[-1])

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

    print(dp[N])

main()

Submission status: Accepted

Solution code:
n = int(input())
dp = list(range(100010))
for i in range(n+1):
    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:
n=int(input())
ans=n
for i in range(n+1):
    cnt=0
    t=i
    while t>0:
        cnt+=t%6
        t//=6
    t=n-i
    while t>0:
        cnt+=t%9
        t//=9
    ans=min(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
    t=N-i
    while t>0:
        cnt+=t%9
        t//=9
    ans=min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
# counts of i yen will be given as cnt[i]
cnt = list(range(n+1))
options = [1]


p = 1
while 9**p <= n:
    options.append(9**p)
    p += 1
p = 1
while 6**p <= n:
    options.append(6**p)
    p += 1

options = sorted(options)
for i in range(n+1):
    for j in options:
        if i>=j:
            """If (i-j) yen could be withdrawn at less than (i-j) times,
            i yen will be done by additional j yen-withdrawal.
            """
            cnt[i] = min(cnt[i], cnt[i-j]+1)

print(cnt[n])

Submission status: Accepted

Solution code:
n = int(input())
# 100000以下の引き出せるお金の候補を作る
# 9**5 = 59049
# 6**6 = 46656

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

# print(li)
DP = list(range(n + 1))

for l in li:
    for j in range(l, n + 1):
        DP[j] = min(DP[j - l] + 1, DP[j])
print(DP[-1])

Submission status: Accepted

Solution code:
n = int(input())
max = 100000
#dp[n] = min(1+dp[n-1], 1+dp[n-6], 1+dp[n-6**2],....1+dp[n-9],1+dp[n-9**2]...)
dp = [float("INF")] * (max+1)
dp[0] = 0
for i in range(1,max+1):
  power = 1
  while power <= i:
    dp[i] = min(dp[i], dp[i-power]+1)
    power *= 6
  power = 9
  while power <= i:
    dp[i] = min(dp[i], dp[i-power]+1)
    power *= 9
print(dp[n])

Submission status: Accepted

Solution code:
n = int(input())

a = n // 9 + 1

ans = 10**10
tmp = 0

for i in range(a):
    six = (n - 9 * i) // 6
    one = (n-9*i-6*six)
    si = six
    nine = i
    tmp = 0
    while nine > 0:
        tmp += nine % 9
        nine = nine // 9
    while six > 0:
        tmp += six % 6
        six = six // 6
    ans = min(ans,tmp+one)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
ans=N
for i in range(N+1):
    cnt=0
    a=i
    while a>0:
        cnt += a%6
        a //= 6
    b=N-i
    while b>0:
        cnt += b%9
        b //= 9
    ans=min(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
    t=N-i
    while t>0:
        cnt+=t%9
        t//=9
    ans=min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
max = 100000
#dp[n] = min(1+dp[n-1], 1+dp[n-6], 1+dp[n-6**2],....1+dp[n-9],1+dp[n-9**2]...)
dp = [float("INF")] * (max+1)
dp[0] = 0
for i in range(1,max+1):
  power = 1
  while power <= i:
    dp[i] = min(dp[i], dp[i-power]+1)
    power *= 6
  power = 9
  while power <= i:
    dp[i] = min(dp[i], dp[i-power]+1)
    power *= 9
print(dp[n])

Submission status: Accepted

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

cnt = N #1円ずつ下ろせばN回で済むため
for i in range(N+1):
    tmp_cnt = 0
    s = 1
    while i >= s:
        tmp_cnt += (i // s) % 6
        s *= 6
    j = N-i
    k = 1
    while j >= k:
        tmp_cnt += (j // k) % 9
        k *= 9
    
    if tmp_cnt < cnt:
#         print(tmp_cnt,i,j)
        cnt = tmp_cnt
        
print(cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

INF = 10 ** 6
dp = [INF] * (10**5+1)
dp[0] = 0

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

print(dp[N])

Submission status: Accepted

Solution code:
import bisect as bi

li6 = [6 ** i for i in range(7)]
li9 = [9 ** i for i in range(6)]

def s69(n):
  if n < 6:
    return n
  else:
    s6 = li6[bi.bisect(li6, n)-1]
    s9 = li9[bi.bisect(li9, n)-1]
    return min(n // s6 + s69(n % s6), 1 + s69(n-s9))
  
print (s69(int(input())))

Submission status: Accepted

Solution code:
import bisect as bi

li6 = [6 ** i for i in range(7)]
li9 = [9 ** i for i in range(6)]

def s69(n):
  if n < 6:
    return n
  else:
    s6 = li6[bi.bisect(li6, n)-1]
    s9 = li9[bi.bisect(li9, n)-1]
    return min(n // s6 + s69(n % s6), 1 + s69(n-s9), n // s9 + s69(n % s9))
  
print (s69(int(input())))

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
    t = n - i
    while t > 0:
        cnt += t % 9
        t //= 9
    ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:

n = int(input())
ans = 100000
for i6 in range(16668):
    count = 0
    n1 = n-i6*6
    if n1>=0:
        j = 0
        while j<=5:
            count = count + (i6%(6**(j+1)))//(6**j)
            i6 -= i6%(6**(j+1))
            j += 1
        j = 0
        i9 = n1//9
        count += n1%9
        while j<=5:
            count += (i9%(9**(j+1)))//(9**j)
            i9 -= i9%(9**(j+1))
            j += 1
        ans = min(ans,count)
print(ans)