1로 만들기 [DP]

#1로 만들기
# 연산 최소로 사용하는 법


n=int(input())
d=[0]*30001

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)
    if i%5==0:
        d[i]=min(d[i],d[i//5]+1)


print(d[n])

• 2부터 N+1까지 iterator가 돈다고 할 때, 배열의 값에 해당 index가 1이되려면 해야 하는 최소한의 연산 횟수를 기록
• (ex) 반복문 내에서 arr[2] = 1이 기록되어 있다면, arr[4]는 arr[i/2] + 1번을 기록해야한다.
  4는 2로 나누어 떨어지고, 2로 나눌 때 1번 연산이 필요한건 기록해 두었으니 arr[4]=arr[2]+1 (1은 현재 2로 나눴을 때의 연산)