[C++] 백준(BAEKJOON) 1463

#include <stdio.h>
using namespace std;
 
int n;
int cache[10000001];
 
int dp(int x){
    if(x == 1)
        return 0;
    
    if(cache[x] > 0)
        return cache[x];
    
    cache[x] = dp(x-1) + 1;
    
    if(x%2 == 0){
        int temp = dp(x/2) + 1;
        if(cache[x] > temp)
            cache[x] = temp;
    }
    
    if(x%3 == 0){
        int temp = dp(x/3) + 1;
        if(cache[x] > temp)
            cache[x] = temp;
    }
    
    return cache[x];
}
 
int main(){
    scanf("%d", &n);
    
    printf("%d", dp(n));
    
    return 0;
}