[BOJ/1463] 1로 만들기 / DP

#연산 재활용 -> dp

X = int(input())

dp = [0] * (X+1) 
# 기본적인 dp 세팅

for i in range(2,X+1):
    dp[i] = dp[i-1] +1
    #그리디로 푼다면 짝수, 홀수로 바로 나눌 수 있지만 
    #이 문제의 경우 경우의 수를 고려하는 최솟값임
    
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2]+1)
    # 

    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3]+1)
    # 

print(dp[X])