atcoder abc99 Strange Bankのpythonの実装

・内容：
貰う DP と配る DP、メモ化再帰、個数制限なしナップサック問題 - Qiita
の記事のbfsでの実装をpythonでやった。

・説明：0から1,6,6*6,,,9,9*9,,,,の辺を取ったグラフと見ればbfsで求められる。詳しくは上の記事を参考。c++ではfor文で6,9の倍数が表現できるがpythonだとそれが少し難しかった。

from collections import deque
n=int(input())

dp=[-1 for _ in range(n+1)]   #-1で未探索。n円までに必要な引き出し回数。

que=deque()
que.append(0)
dp[0]=0

while len(que)!=0:
  p=que.popleft()
  
  #1,6,6*6,,
  i=1
  while p+i<=n:
    if dp[p+i]==-1:
      dp[p+i]=dp[p]+1
      que.append(p+i)
    i*=6
    
  #1,9,9*9,,
  j=1
  while p+j<=n:
    if dp[p+j]==-1:
      dp[p+j]=dp[p]+1
      que.append(p+j)
    j*=9
    
print(dp[n])