[PYTHON] Atcoder ABC099 C --Strange Bank Separate Solution

AtcoderProblem is quite difficult in the latter half of the difficulty level green, but there seem to be various solutions ...

Recursion

saiki.py

# coding: utf-8
# Your code here!
N=int(input())

def saiki(tgt,i,count,ans):
    #print(tgt,i,count,ans,temp[i])

    if i==0 or tgt==0:
        ans=min((tgt+count),ans)
        return ans
        
    num=tgt//temp[i]
    while num>=0:
        ans=saiki(tgt-num*temp[i],i-1,count+num,ans)
        if ans<(count+num):
            return ans
        num-=1
    return ans

temp=[1]
n=1
while N>=6**n:
    temp.append(6**n)
    n+=1
    
n=1
while N>=9**n:
    temp.append(9**n)
    n+=1

temp.sort()

print(saiki(N,len(temp)-1,0,10**9))

I made it when it was brown, so it's a little messy. I don't like recursion because I write an infinite loop

Dynamic programming

dynamic.py

# coding: utf-8
# Your code here!
N=int(input())

lis=[]

temp=6
while temp<=N:
    lis.append(temp)
    temp*=6

temp=9
while temp<=N:
    lis.append(temp)
    temp*=9

lis.sort(reverse=True)

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

#Array dp[N+1]Make a note of the minimum number of steps to make the index number
for item in lis:
    for i in range(N+1):
        if dp[i]!=10**9:
            if i+item<=N:
                dp[i+item]=min(dp[i]+1,dp[i+item])
            
ans=10**10
for index,item in enumerate(dp):
    ans=min(ans,item+N-index)
print(ans)

I thought this was easier and simpler

I was conscious of the solution of knapsack As I noticed later, if you start writing notes in dp like this time from 1, it will be an infinite number of knapsacks, and if you start from the opposite, it will be a limited number of knapsacks.

bfs I don't know I will do it someday