[알고리즘]다이나믹프로그래밍-1로만들기

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

 

1. X가 3으로 나누어 떨어지면 3으로 나눈다.

2. X가 2로 나누어떨어지면 2로나눈다.

3. 1을 뺀다.

 

예제 ) 8 , 10

최소 : 8 4 2 1 (3회)

3으로 먼저 나누려는 경우 : 8 7 6 2 1  (4회)

 

최소 : 10 9 3 1 (3회)

2로 먼저나누려는 경우 : 10 5 4 2 1 (4회)

 

점화식 구하기

2나 3의 배수일 경우 바로 구한다.

아닐경우 -1을 하여 다시 구한다.

 

public static int[] arr;
public static int calc(int n){
	if( n== 1 ){
    	return 0;
    }
    if( arr[n] > 0 ){
    	return arr[n];
    }
    arr[n] = calc( n-1 ) + 1;
    
    //2로 나누어 떨어지는 경우
    if( n%2 == 0 ){
    	int temp = calc( n/2 ) + 1;
        if( arr[n]>temp ){
        	arr[n] = temp;
        }
    }
    //3으로 나누어 떨어지는 경우
    if( n%3 == 0 ){
    	int temp = calc( n/3 ) + 1;
        if( arr[n]>temp ){
        	arr[n] = temp;
        }
    }
    
    return arr[n];
}

public static void main( String args[] ) {
	int n = new Scanner(System.in).nextInt();
    arr = new int[n+1];
    System.out.println( calc(n) );
}