AtcoderProblem is quite difficult in the latter half of the difficulty level green, but there seem to be various solutions ...
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.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
Recommended Posts