Atcoder ABC099 C - Strange Bank 別解集

AtcoderProblemでは難易度緑後半でなかなか難しいが、解法は色々あるみたい、、、

再帰

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

茶色の時に作ったので所々雑ですね
再帰は無限ループ書いちゃったりするのですきじゃない

動的計画法

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

#配列dp[N+1]にインデックスの数字を作るための最小手数をメモっていく
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)

こっちの方が簡単・単純でいいとおもった

意識したのはナップザックの解法
後から見てて気づいたが今回みたいにdpにメモるのを1から始めると無限個数ナップザック、逆から始めると1個限定ナップザックになる

bfs

わからぬ
いつかやる