10. 다이나믹 프로그래밍(1로 만들기)

# 1로 만들기
x = int(input())

d = [0] * 30001
for i in range(2, x+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[x])

Uploaded by Notion2Tistory v1.1.0