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

Recommended Posts

Atcoder ABC099 C --Strange Bank Separate Solution
Atcoder ABC60 D --Simple Knapsack Separate Solution
Atcoder ABC125 C --GCD on Blackboard
Solved AtCoder ABC 114 C-755 with Python3
AtCoder ABC176
AtCoder ABC177
AtCoder ABC 174 Python
AtCoder ABC 098 C --Attention Thinking about the answer
AtCoder ABC187 Python
AtCoder ABC188 Python
Solving with Ruby AtCoder ABC110 C String Manipulation
Challenge AtCoder (ABC) 164 with Python! A ~ C problem
AtCoder ABC 175 Python
Solve Atcoder ABC176 (A, B, C, E) in Python
Atcoder ABC115 Past Exercises
ABC147 C --HonestOrUnkind2 [Python]
[AtCoder explanation] Control ABC180 A, B, C problems with Python!
[AtCoder explanation] Control ABC188 A, B, C problems with Python!
[AtCoder explanation] Control ABC158 A, B, C problems with Python!
Solving with Ruby and Python AtCoder ABC011 C Dynamic programming
AtCoder ABC151 Problem D Speed comparison in C ++ / Python / PyPy
[AtCoder explanation] Control ABC164 A, B, C problems with Python!
[AtCoder explanation] Control ABC168 A, B, C problems with Python!