문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제 입력 1

2

예제 출력 1

1

예제 입력 2

10

예제 출력 2

3

풀이

1. 먼저 작은 문제로 나눠지는지의 여부

x -> x/3
x -> x/2
x -> x-1

x가 전부 작아진다.

예를들어
12를 1로 만든다면
첫번째 연산을 이용해서 12/3 = 4이다.
4에서 1이되는 최소횟수를 우리가 알고 있다고 가정한다면
우리가 원하는 정답은 작은 문제를 이용해서 구할수있다.

12-> 4가 1이되는 횟수(2번) - 3번

12 -> 4 or 6 or 11
4->1 (2번) V
6->1 (2번) V
11->1 (4번)

2. 점화식의 정의 구하기

D[N] = N을 1로 만드는 최소 연산 횟수
N -> [ N/3 -> ......-> 1 ]
------------D[N/3]
= 1+D[N/3]

N -> [ N/2 -> ......-> 1 ]
------------D[N/2]
= 1+D[N/2]

N -> [ N-1 -> ......-> 1 ]
------------D[N-1]

= 1+D[N-1]

D[N] = min(D[N/3] or D[N/2] or D[N-1])+1

Top-Down 방식 소스

import java.util.*;

public class Main {
    public static int[] d;
    public static int go(int n) {
    	//점화식에는 꼭 들어가야하는 코드 
        // 가장 작은 크기일때
        if (n == 1) {
            return 0;
        }
        //memorization
        if (d[n] > 0) {
            return d[n];
        }
        //연산 세번째같은 경우 언제나 -1을 하는 것이다.
        d[n] = go(n-1) + 1;
        //2로 나눠 떨어지는 경우
        if (n%2 == 0) {
            int temp = go(n/2)+1;
            if (d[n] > temp) { //최소값 비교
                d[n] = temp;
            }
        }
         //3으로 나눠 떨어지는 경우
        if (n%3 == 0) {
            int temp = go(n/3)+1;
            if (d[n] > temp) {
                d[n] = temp;
            }
        }
        return d[n];
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        d = new int[n+1];
        System.out.println(go(n));
    }
}

Bottom-up 방식 소스

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] 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] > d[i/2] + 1) {
                d[i] = d[i/2] + 1;
            }
            if (i%3 == 0 && d[i] > d[i/3] + 1) {
                d[i] = d[i/3] + 1;
            }
        }
        System.out.println(d[n]);
    }
}