[BOJ] 1463. 1로 만들기

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] dp = new int [1000001];
		dp[1] = 0;
		dp[2] = 1;
		dp[3] = 1;
		for(int i = 4; i <= N; i++) {
			dp[i] = dp[i-1];
			if(i%2 == 0) dp[i] = Math.min(dp[i/2], dp[i]);
			if(i%3 == 0) dp[i] = Math.min(dp[i/3], dp[i]);
			dp[i] = dp[i]+1;
		}
		System.out.println(dp[N]);
	}
}