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

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

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

import collections
import itertools

def getint(): return int(input())
def getints(): return list(map(int, input().split()))


n = getint()

array6 = [6]
while array6[-1] < n:
    array6.append(6 * array6[-1])

array9 = [9]
while array9[-1] < n:
    array9.append(9 * array9[-1])

cache = [-1] * (n + 1)
def solve(rest):
    res = cache[rest]
    if res >= 0:
        return res
    res = rest

    for m6 in reversed(array6):
        if m6 <= rest:
            res = min(res, solve(rest - m6) + 1)
            break
    for m9 in reversed(array9):
        if m9 <= rest:
            res = min(res, solve(rest - m9) + 1)
            break
    cache[rest] = res
    return res

print(solve(n))

Submission status: Accepted

Solution code:
N = int(input())
dp = [0] * (10**5+10)
for i in range(1,100005):
    dp[i] = float("inf")
    power = 1
    while power <= i:
        dp[i] = min(dp[i], dp[i-power]+1)
        power *= 6
    power2 = 1
    while power2 <= i:
        dp[i] = min(dp[i], dp[i-power2]+1)
        power2 *= 9

print(dp[N])

Submission status: Accepted

Solution code:
n=int(input())
k=[1,6,6**2,6**3,6**4,6**5,6**6,9,9**2,9**3,9**4,9**5]
dp=[n]*(n+1)
dp[0]=0

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

print(dp[n])

Submission status: Accepted

Solution code:
N = int(input())

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

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

print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())

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

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

print(dp[0])

Submission status: Accepted

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

ans = N
for i in range(N+1):
  count = 0
  t=i
  while t>0:
    count+=t%6
    t=math.floor(t/6)

  t = N-i

  while t>0:
    count += t%9
    t=math.floor(t/9)

  if ans>count:
    ans = count

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[1, 6, 36, 216, 1296, 7776, 46656]
b=[1, 9, 81, 729, 6561, 59049]
def ab_cal(num,arr):
  i=len(arr)-1
  cnt1=0
  while num>0:
    if arr[i]<=num:
      num-=arr[i]
      cnt1+=1
    else:
      i-=1
  return cnt1

ans = 10**9
for i in range(0,n+1):
  cnt=ab_cal(i,a)+ab_cal(n-i,b)
  ans=min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
dp = [0]
for i in range(1,n+1):
  can = []
  cnt9 = 1
  cnt6 = 1
  while i >= 9 ** cnt9:
    here = i - 9 ** cnt9
    can.append(dp[here] + 1)
    cnt9 += 1
  while i >= 6 ** cnt6:
    here = i - 6 ** cnt6
    can.append(dp[here] + 1)
    cnt6 += 1
  can.append(dp[i-1] + 1)
  dp.append(min(can))
print(dp[-1])

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import itertools, operator, functools, sys

sys.setrecursionlimit(10 ** 9 + 7)

n = int(input())

amounts = [1]
amounts.extend(itertools.takewhile(lambda x: x <= n, itertools.accumulate(itertools.repeat(6), func=operator.mul)))
amounts.extend(itertools.takewhile(lambda x: x <= n, itertools.accumulate(itertools.repeat(9), func=operator.mul)))
amounts.sort(reverse=True)

@functools.lru_cache(maxsize=None)
def f(x):
    if x == 0:
        return 0
    
    count = float('inf')
    for amount in amounts:
        if x - amount >= 0:
            count = min(count, f(x - amount) + 1)
    return count

print(f(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:
import math

n = int(input())
ans = n
for i in range(n+1):
    cc = 0
    t = i
    while (t > 0):
        cc += t % 6
        t = math.floor(t/6)
    t = n - i
    while (t > 0):
        cc += t % 9
        t = math.floor(t/9)
    ans = min(ans, cc)
print(ans)

Submission status: Accepted

Solution code:
# ABC099C - Strange Bank
# DP ver.
def powers_of_x(x: int, N: int) -> set:
    # return set of x^1, x^2, x^3, ..., x^p ≤ N
    from itertools import count, takewhile

    if x == 1:
        return set()
    ret = set(x ** p for p in takewhile(lambda p: x ** p <= N, count(1)))
    return ret


def main():
    n = int(input())
    dp = [i for i in range(n + 1)]  # initialize with using only ¥1
    cand = powers_of_x(6, n) | powers_of_x(9, n)
    for i in range(n + 1):
        for j in cand:
            if i - j >= 0:
                dp[i] = min(dp[i], dp[i - j] + 1)
    print(dp[-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(300000)

N = int(input())

memo = [None for _ in range(N + 1)]


def f(n):
    if n == 0:
        return 0
    if memo[n] is not None:
        return memo[n]
    ans = n
    pow = 1
    while pow <= n:
        ans = min(ans, f(n - pow) + 1)
        pow *= 6
    pow = 1
    while pow <= n:
        ans = min(ans, f(n - pow) + 1)
        pow *= 9
    memo[n] = ans
    return ans


print(f(N))

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

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

yen = [6 ** i for i in range(1, 8) if 6 ** i <= n]
yen += [9 ** i for i in range(1, 7) if 9 ** i <= n]

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

print(dp[-1])

Submission status: Accepted

Solution code:
# ABC099C - Strange Bank
# DP ver.
def main():
    n = int(input())
    dp = [i for i in range(n + 1)]  # initialize with using only ¥1
    cand = [6 ** i for i in range(1, 7) if 6 ** i <= n]
    cand += [9 ** i for i in range(1, 6) if 9 ** i <= n]
    for i in range(n + 1):
        for j in cand:
            if i - j >= 0:
                dp[i] = min(dp[i], dp[i - j] + 1)
    print(dp[-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC099C - Strange Bank
# DP ver.
def main():
    n = int(input())
    dp = [i for i in range(n + 1)]  # initialize with using only ¥1
    cand = [6 ** i for i in range(1, 7) if 6 ** i <= n]
    cand += [9 ** i for i in range(1, 6) if 9 ** i <= n]
    for i in range(n + 1):
        for j in cand:
            if j > n:
                break
            if i - j >= 0:
                dp[i] = min(dp[i], dp[i - j] + 1)
    print(dp[-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC099C - Strange Bank
# DP ver.
def main():
    n = int(input())
    dp = [i for i in range(n + 1)]  # initialize with using only ¥1
    cand = []  # 6^n, 9^n <= n
    for i in (6, 9):
        p = 1
        while i ** p <= n:
            cand += [i ** p]
            p += 1
    for i in range(n + 1):
        for j in cand:
            if j > n:
                break
            if i - j >= 0:
                dp[i] = min(dp[i], dp[i - j] + 1)
    print(dp[-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC099C - Strange Bank
# DP ver.
def main():
    n = int(input())
    # initialize dp table with using only ¥1
    dp = [i for i in range(n + 1)]
    cand = (6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049)
    for j in cand:
        for i in range(n + 1):
            if j > n:
                break
            if i - j >= 0:
                dp[i] = min(dp[i], dp[i - j] + 1)
    print(dp[-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC099C - Strange Bank
def main():
    n = int(input())
    # initialize dp table with using only ¥1
    dp = [i for i in range(n + 1)]
    cand = (6, 9, 36, 81, 216, 729, 1296, 6561, 7776, 46656, 59049)
    for i in range(n + 1):
        for j in cand:
            if j > n:
                break
            if i - j >= 0:
                dp[i] = min(dp[i], dp[i - j] + 1)
    print(dp[-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, fractions, itertools


def solve(N: int):
    mn = N
    for i in range(N+1):
        s = i
        n = N - i
        sc = 0
        nc = 0
        while(s > 0):
            sc += s % 6
            s //= 6
        while(n > 0):
            nc += n % 9
            n //= 9
        if sc + nc < mn:
            mn = sc + nc
    print(mn)
    return


# Generated by 1.1.4 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())
dp = [10**9]*30000000
dp[0] = 0
pow6 = [6**i for i in range(10) if 6**i <= n]
pow9 = [9**i for i in range(10) if 9**i <= n]

for i in range(n):
    for p6 in pow6:
        dp[i+p6] = min(dp[i+p6], dp[i]+1)
    for p9 in pow9:
        dp[i+p9] = min(dp[i+p9], dp[i]+1)
print(dp[n])

Submission status: Accepted

Solution code:
N = int(input())
dp = [0]
for i in range(1,N+1):
    P = []
    j = 0
    while i >= 6**j:
        P.append(dp[i-6**j]+1)
        j += 1
    j = 0
    while i >= 9**j:
        P.append(dp[i-9**j]+1)
        j += 1
    dp.append(min(P))
print(dp[N])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
l = [0,1,2,3,4,5,1,2,3,1] + [0] * N
j = k = 1
for i in range(10,N+1):
    if i >= 6**(j+1):j+=1
    if i >= 9**(k+1):k+=1
    al = []
    m = i//9**(k)
    for v in range(1,m+1):
        n = i - v*(9**k)
        al.append(v+l[n])
    o = i//6**(j)
    for u in range(1,o+1):
        p = i - u*(6**j)
        al.append(u+l[p])
    l[i] = min(al)
print(l[N])

Submission status: Accepted

Solution code:
n = int(input())

dp = [float('inf')] * (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[-1])

Submission status: Accepted

Solution code:
n = int(input())
li = [1,6,6**2,6**3,6**4,6**5,6**6,9,9**2,9**3,9**4,9**5]
dp = [100000]*100001
dp[0] = 0
for i in range(100001):
  for s in li:
    if i+s <= 100000:
      dp[i+s] = min(dp[i]+1,dp[i+s])
print(dp[n])

Submission status: Accepted

Solution code:
N = int(input())
dp = [0] * 100050
money = set()
i = 0
while(6**i < 10**5):
    money.add(6**i)
    i += 1
i = 0
while(9**i < 10**5):
    money.add(9**i)
    i += 1
mm = []
for i in range(1, 10**5+1):
    if i in money:
        mm.append(i)
    dp[i] = min([dp[i-k] for k in mm]) + 1

print(dp[N])

Submission status: Accepted

Solution code:
n = int(input())
ans = n

for i in range(n//6+1):
    cnt = 0
    k = i
    while k != 0:
        cnt += k % 6
        k = k // 6
    j = (n-i*6) // 9
    k = j
    while k != 0:
        cnt += k % 9
        k = k // 9
    ans = min(ans, cnt+(n-i*6-j*9))

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

def sum(money,p):
	count = 0
	while money:
		count += money%p
		money = money // p
	return count

ans = 10**6
for i in range(n+1):
	ans = min(ans,sum(i,6)+sum(n-i,9))

print(ans)

Submission status: Accepted

Solution code:
#import time
#start = time.time()

n = int(input())
ls = [1]
t = 6
while t < 100000:
    ls.append(t)
    t *= 6
t = 9
while t < 100000:
    ls.append(t)
    t *= 9

ls.sort()
#print(ls)
"""
cnt = 0
while n >= 6:
    print(n,ls)
    ls = [i for i in ls if i <= n]
    n -= ls[len(ls)-1]
    cnt += 1
print(cnt+n)
"""
#dp[n] n円を引き出すために必要な回数
dp = [10**9 for i in range(n+1)]
dp[0] = 0

for i in range(1,n+1):
    ls1 = [j for j in ls if j <= i]
    #print(ls1)
    for j in range(len(ls1)):
        #print(i,i-ls1[j])
        dp[i] = min(dp[i],dp[i - ls1[j]] + 1)

print(dp[n])

#process_time = time.time() - start

#print(process_time)

Submission status: Accepted

Solution code:
n = int(input())
dp = [10**9]*30000000
dp[0] = 0
pow6 = [6**i for i in range(10) if 6**i <= n]
pow9 = [9**i for i in range(10) if 9**i <= n]

for i in range(n):
    for p6 in pow6:
        dp[i+p6] = min(dp[i+p6], dp[i]+1)
    for p9 in pow9:
        dp[i+p9] = min(dp[i+p9], dp[i]+1)
print(dp[n])

Submission status: Accepted

Solution code:
def sum_digits(n, m):
    r = 0
    while n:
        r = r + n % m
        n = n // m
    return r

N = int(input())

ans = 100000
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())
dp = [0] * (N + 1)
dp[0] = 0
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 = [0] * (n + 1)
a = 9
b = 6
for i in range(1, n + 1):
    if a * 9 <= i: a *= 9
    if b * 6 <= i: b *= 6
    if i - a >= 0:
        if i - b >= 0:
            dp[i] = min(dp[i - a], dp[i - b], dp[i - 1]) + 1
        else:
            dp[i] = min(dp[i - a], dp[i - 1]) + 1
    elif i - b >= 0:
        dp[i] = min(dp[i - b], dp[i - 1]) + 1
    else:
        dp[i] = dp[i - 1] + 1
print(dp[-1])

Submission status: Accepted

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

ans = N
for i in range(N + 1):
    c = 0
    res = i
    while res > 0:
        c += res % 6
        res //= 6
    res = N - i
    while res > 0:
        c += res % 9
        res //= 9
    ans = min(ans, c)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

def base10to(n, b):
    if (int(n/b)):
        return base10to(int(n/b), b) + str(n%b)
    return str(n%b)

mod9 = N//9
res = 10**10

for i in range(0,mod9+1):
    j = (N-i*9)//6
    cnt = 0
    if 9*i+6*j > N:
        break
    else:
        t = base10to(i,9)
        s = base10to(j,6)
        for x in str(t):
            cnt += int(x)
        for y in str(s):
            cnt += int(y)
        cnt += (N-9*i-6*j)
        if cnt <= res:
            res = cnt
print(res)

Submission status: Accepted

Solution code:
N = int(input())
ans = N
for i in range(N+1):
  t = i
  cc = 0
  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:
N = int(input())


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

    t = N-i
    while t > 0:
        cc += t % 9
        t //= 9

    if ans > cc:
        ans = cc

print(ans)

Submission status: Accepted

Solution code:
N = int(input())


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

    t = N-i
    while t > 0:
        cc += t % 9
        t //= 9

    if ans > cc:
        ans = cc

print(ans)

Submission status: Accepted

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

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

print(dp[N])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
N = int(input())
dp = [10**15] * 1000000
dp[1] = 1
dp[0] = 0
for i in range(N + 1):
    dp[i + 1] = min (dp[i] + 1 , dp[i + 1])
    for k in range(7):
        dp[i + 6 ** k ] = min (dp[i] + 1 ,dp[i + 6 ** k ])
    for k in range( 7):
        dp[i + 9 ** k] = min(dp[i] + 1, dp[i + 9 ** k])
print(dp[N])

Submission status: Accepted

Solution code:
from functools import reduce
import math
import bisect

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    N = int(input())
    N_max = 100000
    l = []
    l.append(1)
    tmp = 1
    while tmp < N_max:
        tmp *= 6
        l.append(tmp)
    tmp = 1
    while tmp < N_max:
        tmp *= 9
        l.append(tmp)
    l.sort()
    d = [N_max for _ in range(N+1)]
    d[0] = 0
    for i in range(1,N+1):
        d[i] = d[i-1] + 1
        for j in range(len(l)):
            if i >= l[j]:
                d[i] = min(d[i],d[i-l[j]]+1)
    print(d[N])
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections

N = int(input())

withdraw = []
withdraw.append(1)
i = 1
while 6 ** i < 100000:
    withdraw.append(6 ** i)
    i += 1
i = 1
while 9 ** i < 100000:
    withdraw.append(9 ** i)
    i += 1
withdraw = sorted(withdraw)

# 残り12ってときに、6, 6だと最小だが貪欲だと9, 1, 1, 1になっちゃう。
# 幅優先探索して最初に0になったものが最短。
# nodeは(残り金額, depth)
memo = set([N])
q = collections.deque([(N, 0)])
while len(q) > 0:
    n, depth = q.popleft()
    if n == 0:
        print(depth)
        break
    for w in withdraw:
        if n >= w and n-w not in memo:
            q.append((n-w, depth+1))
            memo.add(n-w)

Submission status: Accepted

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

pow6=[6**j for j in range(10) if 6**j <= N]
pow9=[9**j for j in range(10) if 9**j <= N]

for i in range(N):
    for p6 in pow6:
        dp[i+p6]=min(dp[i+p6], dp[i]+1)
    for p9 in pow9:
        dp[i+p9]=min(dp[i+p9], dp[i]+1)

print(dp[N])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC99 C

#6^pを6回引き出すとき6^(p+1)と等しい
#6^pは(n//6^p)%6回のみ引き出す
#9^pも同様
#6^pと9^qを全探索
n = int(input())
ans = n
for i in range(0,n+1,6):
    cnt = 0
    j = n-i#i:=6^pに用いる,j:=9^pに用いる
    while i > 0:
        cnt += i%6#6^p何回用いるか
        i //= 6
    while j > 0:
        cnt += j%9#9^p何回用いるか
        j //= 9
    ans = min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:

coin_list = sorted([1] + [ 6**i for i in range(1,7) ] + [ 9**i for i in range(1,6) ])

num_list = [ i for i in range(10**5+1) ]

for i in range(1,10**5+1):
    candidate = [ num_list[i-j] for j in coin_list if j <= i ]
    num_list[i] = min(candidate) + 1

n = int(input())
print(num_list[n])

Submission status: Accepted

Solution code:
def smaller(x, y):
	if x < y: return x
	return y

lst = [1]
x = 6
while x <= 100000:
	lst.append(x)
	x *= 6
x = 9
while x <= 100000:
	lst.append(x)
	x *= 9
lst.sort()

N = int(input())
dp = []
for i in range(0, N+1):
	dp.append(100001)
dp[0] = 0
for i in range(0, N):
	for j in range(0, len(lst)):
		if i + lst[j] > N:
			break
		dp[i+lst[j]] = smaller(dp[i+lst[j]], dp[i]+1)
print(dp[N])

Submission status: Accepted

Solution code:
N = int(input())
xs = [1]
i = 1
while N >= 6**i:
    if 9**i <= N:
        xs.append(9**i)
    xs.append(6**i)
    i += 1
X = sorted(xs)
# print(X)

# N円のときの最小回数
dp = [10000000000] * 1008000
dp[0] = 0
for i in range(N):
    for x in X:
        dp[i+x] = min(dp[i]+1, dp[i+x])
print(dp[N])

Submission status: Accepted

Solution code:
def resolve():
    n = int(input())
    a = [1]
    x = 6
    while x<=n:
        a.append(x)
        x=x*6
    x = 9
    while x<=n:
        a.append(x)
        x=x*9
    a = list(set(a))
    a.sort()
    dp = [10**9]*(n+5)
    dp[0]=0
    for i in range(1,n+1):
        for j in a:    
            if(i>=j):
                dp[i]=min(dp[i],dp[i-j]+1)
            else:
                break
    print(dp[n])


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

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

if __name__ == "__main__":
    n = int(input())
    l = [1] + [6**i for i in range(1, 8) if 6**i <= n] + [9**i for i in range(1, 7) if 9**i <= n]
    l.sort()

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

    for i in range(n):
        for e in l:
            if i + e <= n:
                dp[i+e] = min(dp[i] + 1, dp[i+e])
            else:
                break

    print(dp[n])

Submission status: Accepted

Solution code:
n = int(input())

ans = n
for i in range(n+1):
    tmp_ans = 0
    m = i
    while m > 0:
        tmp_ans += m % 6
        m = m // 6
    m = n - i
    while m > 0:
        tmp_ans += m % 9
        m = m // 9

    ans = min(ans, tmp_ans)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def Joulist(n, m):
    ans = []
    i = m // 3
    while i <= n:
        ans.append(i)
        i *= m
    return ans


n = int(input())
dp = [1000000] * (n//3 + 1)
dp[0] = 0
for i in range(2, n//3+1):
    kouho = Joulist(i, 6) + Joulist(i, 9)
    dp[i] = min([dp[i-k] for k in kouho]) + 1
if n != 3:
    print(dp[n//3] + n%3)
else:
    print(3)

Submission status: Accepted

Solution code:
n = int(input())

# dp = [float("INF")] * 100010
# dp[0] = 0
dp = [x for x in range(1000010)]


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


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


ans = dp[n]
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

# W = int(stdin.readline().rstrip())
# N, K = [int(x) for x in stdin.readline().rstrip().split()]
# shot = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(N)]
# dp = [[0] * (W + 1) for k in range(N + 1)]
#
# for i in range(N):
#     for w in range(W):
#         if w + 1 >= shot[i][0]:
#             dp[i + 1][w + 1] = max(dp[i + 1][w + 1], dp[i][w + 1 - shot[i][0]] + shot[i][1])
#         dp[i + 1][w + 1] = max(dp[i][w + 1], dp[i + 1][w + 1])
#
# print(dp)

N = int(stdin.readline().rstrip())
dp = [k for k in range(N + 1)]

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

print(dp[N])

Submission status: Accepted

Solution code:
# PyPy 推奨
n = int(input())

dp = [float("INF")] * 1000010
dp[0] = 0


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


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


ans = dp[n]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

dp = [float("INF")] * 1000010
dp[0] = 0


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


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


ans = dp[n]
print(ans)

Submission status: Accepted

Solution code:
N=int(input())

m=[1,6,6**2,6**3,6**4,6**5,6**6,9,9**2,9**3,9**4,9**5]
m.sort()
cnt=[0]*(N+1)
for i in range(1,N+1):
    #print('i',i)
    formararr=[]
    for l in m:
        #print('l',l)
        if i>=l:
            formararr.append(cnt[i-l])
        cnt[i]=min(formararr)+1
print(cnt[N])

Submission status: Accepted

Solution code:
n = int(input())

l6 = [6**i for i in range(1,7)]
l9 = [9**i for i in range(1,6)]

l = [1]+l6+l9

dp=[10**8 for _ in range(n+1)]

for i in range(1,n+1):
    for j in l:
        if i == j:
            dp[i]= 1
        elif i>j:
            if dp[i-1]!=0:
                dp[i] = min(dp[i],dp[i-j]+1)
            else:
                pass

print(dp[n])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np
import statistics
from statistics import mean, median,variance,stdev
import math

def main():
	N = int(input())
	
	DP = [i for i in range(100010)]
	
	for i in range(1, 100001):
		for j in range(1, i):
			step = 6**j
			if step > i:
				break
			tmp = 1 + DP[i-step]
			DP[i] = min(DP[i], tmp)
			
	for i in range(1, 100001):
		for j in range(1, i):
			step = 9**j
			if step > i:
				break
			tmp = 1 + DP[i-step]
			DP[i] = min(DP[i], tmp)
	
	print(DP[N])
			
	
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
N = int(input())
 
DP = list(range(N+1))
L = []

i = 1
while True:
    if 6**i > N:
        break
    L.append(6**i)
    i += 1
 
i = 1
while True:
    if 9**i > N:
        break
    L.append(9**i)
    i += 1

for l in sorted(L):
    for j in range(l, N+1):
        DP[j] = min(DP[j], DP[j-l] + 1)

print(DP[-1])

Submission status: Accepted

Solution code:
def Joulist(N,m):#mのk乗としてN以下のもののリスト
    ans = []
    i = m//3
    while i<=N:
        ans.append(i)
        i *= m
    return ans
    
#1円は考えず、N//3円を2円＆3円で引き出してから帳尻を合わせる
N=int(input())
DP = [1000000] * (N//3 + 1)#0円から33333円まで
DP[0] = 0
for i in range(2,N//3 + 1):
    kouho = Joulist(i,6)+Joulist(i,9)
    DP[i] = min([DP[i-k] for k in kouho]) + 1
if N!=3:print(DP[N//3] + N%3)
else:print(3)

Submission status: Accepted

Solution code:
N = int(input())

dp = [10**6] * (N+1)
dp[0] = 0
# 配る DP --- dp[n] から遷移を出して行く
for i in range(N):
    pow6 = 1
    pow9 = 1
    while i + pow6 <= N:
        dp[i+pow6] = min(dp[i+pow6], dp[i]+1)
        pow6 *= 6
    while i + pow9 <= N:
        dp[i+pow9] = min(dp[i+pow9], dp[i]+1)
        pow9 *= 9
print(dp[N])

Submission status: Accepted

Solution code:
n = int(input())
ans = n
for i in range(n + 1):
  cnt, t = 0, 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:
# ABC099C - Strange Bank
def main():
    n = int(input())
    ans = n  # 1yen * n
    for i in range(n + 1):
        cnt, t = 0, 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)


if __name__ == "__main__":
    main()