1로 만들기

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최소값을 출력

10: 9 (-1) -> 3 (%3) -> 3 (%3) -> 1

d[n] = 연산 세 개로 1을 만드는 횟수의 최소값 정의

큰 수로 먼저 나누는게 이득인지 알 수 없다. 모든 경우의 수 중 최소값 택한다.

d[1] = 0
d[2] = 1 (%2 + d[1])
d[3] = 1 (%3 + d[1])
d[4] = 2 (%2 + d[2], -1 + d[3]])
d[5] = 3 (-1 + d[4])
d[6] = 2 (%3 + d[2], %2 + d[3], -1 + d[5])

d = new int[N+1];
Arrays.fill(d,  Integer.MAX_VALUE);
d[1] = 0;

for (int i = 2; i <= N; i++) {
    
    d[i] = Math.min(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);
}