[알고리즘_dp] 백준, 1로 만들기 1463번

//1로 만들기
//https://www.acmicpc.net/problem/1463

package dp;

import java.util.Scanner;

public class backjoon_1463 {
    static int[] d = null;

    public static int to_1(int n){
        if(d[n] > 0){
            return d[n];

        }

        if(n<=1){
            return 0;

        }else{
            d[n] = to_1(n-1) + 1;

            if(n%3==0){
                d[n] = Math.min(to_1(n/3) + 1, d[n]);
            }

            if(n%2==0){
                d[n] = Math.min(to_1(n/2) + 1, d[n]);
            }

            return d[n];
        }


    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        d = new int[n+1];

        System.out.println(to_1(n));
    }
}