BJ1463 1로 만들기

https://www.acmicpc.net/problem/1463

DP 또는 재귀함수를 이용해 해결할 수 있다.

이 문제에서는 재귀함수를 이용했을 때 실행시간이 더 짧았지만, 여러 테스트 케이스를 출력한다면 DP를 활용할 때는 단순히 배열에 접근해 값만 가져오면 되기 때문에 DP가 유리하다.

package day0331;

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

public class MakeOne {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer st;
	static int max_cnt = Integer.MAX_VALUE;
	static void func(int X, int cnt) {
		if(cnt >= max_cnt) {
			return;
		}
		if(X == 1 && cnt < max_cnt) {
			max_cnt = cnt;
		}
		if(X % 3 == 0) func(X / 3, cnt + 1);
		if(X % 2 == 0) func(X / 2, cnt + 1);
		func(X - 1, cnt + 1);
	}
	public static void main(String[] args) throws IOException {
		int X = Integer.parseInt(br.readLine());
		/*func(X, 0);
		bw.append(max_cnt + "");
		bw.flush();
		*/
		int[] DP = new int[X + 1]; // DP 테이블

        for (int i = 2; i <= X; i++) {
            int min = 1 + DP[i - 1];
            if (i % 3 == 0 && 1 + DP[i / 3] < min) min = 1 + DP[i / 3];
            if (i % 2 == 0 && 1 + DP[i / 2] < min) min = 1 + DP[i / 2];
            DP[i] = min;
        }

        System.out.println(DP[X]);
	}
}