다이나믹 프로그래밍_1463 번 : 1로 만들기 JAVA

 

재귀 호출을 이용하여 푼다. 재귀 호출을 하면서 동시에 count를 증가시킨다. N=1되기 전까지 count를 누적시키다 N이 1이 된다면 count를 return시킨다.

N을 각각 2와 3으로 나누면, count에는 +1에 각 연산의 나머지값을 더한 값이 들어간다. 나머지값은 빼기 1 했을때 count와 같기 때문이다. 재귀 호출을 이용하므로  다이내믹 프로그래밍 Top-down 방식이다.

 

import java.io.*;

public class Main{
	public static void main(String[] args){
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        System.out.println(recur(N,0));
    }
    public static int recur(int N, int count){
    	if(N<2)
        	return count;
        return Math.min(recur(N/3,count+1+(N%3)),recur(N/2,count+1+(N%2)));
    }
}

 

다음은 Bottom-up 방식을 이용한 풀이이다.

풀이 절차는 다음과 같다.

1. 테이블식 정의

2. 점화식 찾기

3. 초기값 정하기

 

테이블식 정의

D[i]에는 i가 1을 만들때 연산하는 횟수의 최솟값

 

점화식 찾기

D[i] = Math.min(3으로 나눌때, 2로 나눌때, 1로 뺄 때)

만약 3이 온다면 3으로 나누면 1이 된다. 1은 횟수의 최솟값이 0이고 3에서 3을 나눴을 때 연산이 추가되었으므로 D[1] 값에서 1을 추가한다.

 

초기값 찾기

D[0] = D[1] = 1

 

import java.io.*;

public class Main{
	public static void main(String[] args){
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        System.out.println(countMake1(N));
    }
    public static int countMake1(int N){
    	int[] D = new int[N+1];
        D[0] = 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);
        }
        return D[N];
    }
}