DP 테이블 d[n]은 n이라는 숫자가 1이 되기위해 연산해야 하는 숫자를 의미한다.
보텀업 방식으로 2,3, ... 라는 숫자가 1이 되기 위해 필요한 최소 연산 횟수를 구하고 최종적으로 x라는 숫자가 1이 되기 위해 필요한 최소 연산 횟수를 구해본다.
d[0]은 사용 안할거고 d[1] = 0 이라는 값을 이용한다.
d[2]일 때 2라는 숫자가 1이 되기 위해 필요한 연산 횟수를 구해본다.
1을 빼는 경우에 d[2] = 1이 되고 2,3,5로 나누어 떨어지는 경우도 고려해본다.(1보다 작을 경우는 없긴하지만)
최종적으로 2가 1이 되기 위한 값 d[2] = 1 이 된다.
d[3]일 때 3이라는 숫자가 1이 되기 위해 필요한 연산 횟수를 구해본다.
1을 빼고 2라는 숫자가 1이 되기 위해 필요한 연산 횟수를 더하면 d[3] = 2가 된다.
나머지의 경우에서 3은 3으로 나누어 떨어지기에 d[3] = 1이 된다.
d[4]일 때 4라는 숫자가 1이 되기 위해 필요한 연산 횟수를 구해본다.
1을 빼는 경우에 3으로 만들고 3으로 나누는 연산을 수행하면 d[4] = 2가 된다.
나머지의 경우에서 4는 2로 나누어 떨어지기에 d[4] = d[2] + 1 = 2가 된다.
d[5]일 때 5라는 숫자가 1이 되기 위해 필요한 연산 횟수를 구해본다.
5로 나누어 떨어지므로 d[5] = 1이 된다.
d[6]일 때 6이라는 숫자가 1이 되기 위해 필요한 연산 횟수를 구해본다.
1을 빼는 경우에 5로 만들고 5로 나누는 연산을 수행하면 d[6] = 2가 된다.
나머지의 경우에서 6은 3으로 나누어 떨어지기에 d[6] = 2가 된다.(6을 3으로 나누고 3을 3으로 나누고)
★★ 나누어 떨어지는 값에 대해서 + 1을 해줘야함에 유의해야한다!!
d[14]일 때 14라는 숫자가 1이 되기 위해 필요한 연산 횟수를 구해본다.
최소 연산은 2로 나누어 떨어지므로 2로 나눈다.
-> 나누어 떨어진 수가 1이 되기 위한 최소 연산 횟수 + 1를 해준다.
7은 -1 하고 d[6]하면 되므로 d[7] = 3
따라서 d[14] = 4가 된다.
중요한 것은 나누어 떨어지는 경우에는 나누어 떨어진 수가 1이 되기 위해 필요한 연산 횟수를 더해줘야 한다는것
14 16 18 모두 2로 나누어 떨어지지만 그 값은 7 8 9 이므로 추가적으로 필요한 연산횟수가 각각 다르다!!
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int x = sc.nextInt();
int[] d = new int[x+1];
// 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업)
for (int i = 2; i <= x; i++) {
// 현재의 수에서 1을 빼는 경우
d[i] = d[i - 1] + 1;
// 현재의 수가 2로 나누어 떨어지는 경우
if (i % 2 == 0) d[i] = Math.min(d[i], d[i / 2] + 1);
// 현재의 수가 3으로 나누어 떨어지는 경우
if (i % 3 == 0) d[i] = Math.min(d[i], d[i / 3] + 1);
// 현재의 수가 5로 나누어 떨어지는 경우
if (i % 5 == 0) d[i] = Math.min(d[i], d[i / 5] + 1);
}
System.out.println(Arrays.toString(d));
}
}