[伯俊/Python]制作14631

https://www.acmicpc.net/problem/1463

アルゴリズム分類

動的プログラミング

問題を解く

ダイナミックプログラミングの典型的な問題.
グリディのやり方で近づくことはできない.
d[i]iを1にした演算回数を記憶する.
d[0]またはd[1]の演算回数は0であるため、1とする.
nが10の6乗の場合のインデックスは10の6乗であるため,dの範囲は10**6+1である.

ソースコード

n=int(input())
d=[0]*(10**6+1)

for i in range(2, n+1):
  d[i]=d[i-1]+1
  if i%2==0:
    d[i]=min(d[i], d[i//2]+1)
  if i%3==0:
    d[i]=min(d[i], d[i//3]+1)

print(d[n])