이 문제는 DP 알고리즘을 적용하면 쉽게 풀 수 있습니다.
N(구하고자 하는 수)
D[1] = 0 초기화 // 1일때 연산 불필요
for(i -> 2 ~ N) {
D[i] = D[i-1] + 1
if(2의 배수) D[i / 2] + 1이 D[i]보다 작으면 변경하기 // 나누기 2 연산
if(3의 배수) D[i / 2] + 1이 D[i]보다 작으면 변경하기 // 나누기 3 연산
}
D[N] 출력
바텀-업 형식의 DP알고리즘으로 구현하면 다음과 같습니다.
import java.util.Scanner;
public class Q1463 {
static int N;
static int D[];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
D = new int[N + 1];
D[1] = 0;
for (int i = 2; i <= N; i++) {
D[i] = D[i - 1] + 1;
if (i % 2 == 0) D[i] = Math.min(D[i], D[i / 2] + 1);
if (i % 3 == 0) D[i] = Math.min(D[i], D[i / 3] + 1);
}
System.out.println(D[N]);
}
}