#1463

#1463

문제

풀이

N=int(input())

dp=[0 for _ in range(N+1)]

for i in range(2,N+1):
    #3번째 방식인 1로 뺀다고 생각했을때
    dp[i]=dp[i-1]+1
    
    #2번째방식인 2로 나누어 떨어질때 1번과 2번방식을 비교 
    if i%2==0 and dp[i]>dp[i//2]+1:
        dp[i]=dp[i//2]+1
    
    #3번째방식인 2로 나누어 떨어질때 1번과 3번방식을 비교
    if i%3==0 and dp[i]>dp[i//3]+1:
        dp[i]=dp[i//3]+1
        
print(dp[N])

우선 1을 빼주는걸 먼저 생각하고 2를 나누는것과 3으로 나누는것과 비교를 통해 1로 뺀 경우가 수가 더 클 경우 나누어주는 방식을 택하는 것으로 한다.