1로 만들기

package Jun_2020_05_11;

import java.util.Scanner;

public class 1로 만들기 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		ham(N, 0);
		System.out.println(min);
	}

	static int min = Integer.MAX_VALUE;

	static void ham(int N, int cnt) {
		if (N == 1) {
			min = Math.min(min, cnt);
			return;
		}
		if (N < 1)
			return;
		if (cnt + 1 >= min)
			return;
		if (N % 3 == 0)
			ham(N / 3, cnt + 1);
		if (N % 2 == 0)
			ham(N / 2, cnt + 1);
		ham(N - 1, cnt + 1);
	}
}