백준 1463 1로 만들기 (Python)

다이나믹 프로그래밍

방법 바로 생각하기 은근 까다롭다.

def dynamic_prog(num, dp):

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

        if i % 2 == 0:
            dp[i] = min(dp[i], dp[i//2] + 1)
    print(dp[num])


N = int(input())
dp = [0] * (N+1)
dynamic_prog(N, dp)