[백준][동적 계획법1] 1463 . 1로 만들기(파이썬/Python)

import sys
input = sys.stdin.readline

n = int(input())

#1부터 사용하는 것으로 쓰기 위함
dp = [0] * (n+1)

for i in range(2,n+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[n])

# 메모이제이션(memoization) 기법을 사용

 

# 한 번 사용하는 것을 중복해서 사용하지 않고 저장한 것을 이용해서 사용하는 기법.

 

# 그리디와 다른 점은 최적의 해를 찾기 위해서 냅다 3을 나눠서 시작하는 것과 다르게 최적의 해를 구하려면 모든 경우를 써봐야 안다는 점에서 DP를 사용하는 것.