백준 1463번 문제

1로 만들기

동적계획법의 경우 top-down 방식을 사용할 경우 재귀함수를 호출하는 형태로 진행한다.

반대로 bottom-up 방식을 사용한다면 시작지점부터 for문을 이용해 모든 값을 구해나나는 형태이다.

[top-down] 방식

package DynamicPrograming;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_1463 {
    public static int dp[];
    public static void main(String[] argv) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        dp=new int[N+1]; //초기값 0
        System.out.println(Dynamic(N));

    }
    public static int Dynamic(int N){
        if(N==1) return 0;
        if(dp[N]>0) return dp[N];
        dp[N] = Dynamic(N-1)+1;
        if(N%3==0) dp[N] = Math.min(dp[N],Dynamic(N/3) +1);
        if(N%2==0) dp[N] = Math.min(dp[N],Dynamic(N/2) +1);
        return dp[N];

    }

}

1463번 문제의 경우 나누기3 나누기2 빼기 1 연산을 사용해 N을 1로 만든 최적 경로를 알려주는 문제이다. 그렇게 하기 위해서 재귀함수를 호출해 값을 얻어 가는데 이 과정에서 dp[N]의 값을 dp[N-1]+1로 설정해둔 후 나누기 연산이 가능한 경우 이전에 나눈 수와 비교와 더 작은 값을 출력하고 나누기 연산을 한번 했기 때문에 +1을 해주는 방식으로 문제를 풀었다.

[bottom-up] 방식

package DynamicPrograming;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main2_1463{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int dp[] = new int[N+1];
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i <= N; i++){
            dp[i] = dp[i-1] + 1;
            if (i % 2 == 0) dp[i] = Math.min(dp[i], dp[i/2] + 1);
            if (i % 3 == 0) dp[i] = Math.min(dp[i], dp[i/3] + 1);
        }
        System.out.println(dp[N]);
        br.close();

    }
}