ToOne.java

import java.util.Scanner;

/**
 * Created by yaboong on 2018. 2. 26..
 */
public class ToOne {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        int[] dp = new int[N+1];

        dp[0] = -1;
        dp[1] = 0;
        for (int n=2; n<=N; n++) {
            dp[n] = dp[n-1] + 1;
            if (n % 2 == 0 && dp[n] > dp[n/2] + 1)
            {
                dp[n] = dp[n/2] + 1;
            }
            if (n % 3 == 0 && dp[n] > dp[n/3] + 1)
            {
                dp[n] = dp[n/3] + 1;
            }
        }
        System.out.println(dp[N]);
    }
}