백준 알고리즘 1463번 1로 만들기(python)

기본적인 다이나믹 프로그래밍 문제이다.

N = int(input())
li = [1000001]*(N+1)
li[1] = 0
for i in range(1, N+1):
    if i%3 == 0:
        li[i] = min(li[i], li[i//3]+1) 
    if i%2 == 0:
        li[i] = min(li[i], li[i//2]+1)
    li[i] = min(li[i], li[i-1]+1)
print(li[N])