Baekjoon 1463

문제

Solved.ac Class3

1차시도

public class Main {
	private static int[] data;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int x = Integer.parseInt(br.readLine());

		data = new int[x + 1];
		data[0] = -1;
		data[1] = -1;

		System.out.println(solve(x));

	}

	private static int solve(int x) {

		if (data[x] == 0) {
			if (x % 6 == 0) {
				int a = solve(x - 1);
				int b = solve(x / 3);
				int c = solve(x / 2);
				data[x] = Math.min(a, Math.min(b, c));

			} else if (x % 3 == 0) {
				int a = solve(x - 1);
				int b = solve(x / 3);
				data[x] = Math.min(a, b);

			} else if (x % 2 == 0) {
				int a = solve(x - 1);
				int b = solve(x / 2);
				data[x] = Math.min(a, b);
			} else {
				data[x] = solve(x - 1);
			}
		}
		return data[x] + 1;
	}
}

시간초과

n차시도

DP는 크게 3가지를 기억해야 한다고 한다.
1. 테이블 정의
2. 점화식 찾기
3. 초기값 정하기
테이블은 점화식을 위해 기본적으로 생성하는 배열이고
문제를 대입하면

1. x값이 최소가 되게하는 table[x] 값이다
2. 크게 top - bottom, bottom - top 방식인데
   1. top - bottom
   위 방식은 데이터를 top부터 시작해서 재귀를 이용하여 가장 아래까지 도달한다.
   문제에 대입하면 table[x] 를 찾기위해 3가지 모두를 해보면서, 가장 작은수를 아래부터 찾아간다.
   2. bottom - top
   위 방식은 데이터를 아래부터 시작해서 for문을 이용하여 목표까지 찾는다
   문제에 대입하면 table[2] 부터 시작하여 table[x] 를 찾는다.
3. 초기값은 기본 설정값으로 문제에서는 table[0], table[1] 을 0으로 설정해야 한다.

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int x = Integer.parseInt(br.readLine());

		int[] data = new int[x + 1];
		data[0] = 0;
		data[1] = 0;

		for (int i = 2; i < x + 1; i++) {
			data[i] = data[i - 1] + 1;
			if (i % 2 == 0) {
				data[i] = Math.min(data[i], data[i / 2] + 1);
			}
			if (i % 3 == 0) {
				data[i] =Math.min(data[i], data[i / 3] + 1);
			}
		}
		System.out.println(data[x]);
	}
}

성공