[PYTHON] Atcoder ABC099 C - Separate Bank Separate Lösung

AtcoderProblem ist in der zweiten Hälfte des grünen Schwierigkeitsgrades ziemlich schwierig, aber es scheint verschiedene Lösungen zu geben ...

Rekursiv

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

Ich habe es geschafft, als es braun war, also ist es ein bisschen chaotisch. Ich mag keine Wiederholungen, weil ich Endlosschleifen schreibe

Dynamische Planungsmethode

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]Notieren Sie sich die Mindestanzahl von Schritten, um die Indexnummer zu erstellen
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)

Ich fand das einfacher und einfacher

Ich war mir der Lösung des Rucksacks bewusst Wie ich später bemerkte, wird es eine unendliche Anzahl von Rucksäcken geben, wenn Sie wie diesmal ab 1 in dp schreiben, und wenn Sie vom Gegenteil ausgehen, wird es eine begrenzte Anzahl von Rucksäcken sein.

bfs Ich weiß es nicht Ich werde es eines Tages tun