[백준] 1로 만들기 1463번 - java

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		minCount = new int[n+1];
		
		System.out.println(makeOne(n));
	}

	private static int[] minCount;
	private static int makeOne(int n) {
		if(n <= 1 || minCount[n] != 0) return minCount[n];
		
		if(n%6 == 0) {
			return minCount[n] = Math.min(makeOne(n/3), makeOne(n/2)) + 1;
		}
		if(n%3 == 0) {
			return minCount[n] = Math.min(makeOne(n/3), makeOne(n-1)) + 1;
		}
		else if(n%2 == 0) {
			return minCount[n] = Math.min(makeOne(n/2), makeOne(n-1)) + 1;
		}
		
		return minCount[n] = makeOne(n-1) + 1;
	}
}