[백준] 1463번 - 1로 만들기

 

dp문제이다. 점화식을 세우기는 간단했지만 10 같은 경우는 10 -> 5-> 4 -> 2-> 1보다 10 -> 9 -> 3 -> 1 이 더 최적의 수라고 할 수 있다. 따라서 Math.min을 이용하여 각자의 값 중 작은 값들을 배열에 저장하여 그 값을 출력하면 된다.

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

public class p1463 {
	public static Integer[] ary;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

		ary = new Integer[a + 1];

		ary[0] = 0;
		ary[1] = 1;
		System.out.println(func(a));
	}

	public static int func(int a) {
		if(ary[a] == null) {			
			if (a % 6 == 0) {
				ary[a] = Math.min(func(a / 3), Math.min(func(a / 2), func(a - 1))) + 1;
			} else if (a % 3 == 0) {
				ary[a] = Math.min(func(a / 3), func(a - 1)) + 1;
			} else if (a % 2 == 0) {
				ary[a] = Math.min(func(a / 2), func(a - 1)) + 1;
			} else {
				ary[a] = func(a - 1) + 1;
			}
		}
		return ary[a];
	}
}

 

 

점화식을 세우는 부분이 아직 미숙해서 2와 3의 최소 공배수인 6으로 나누어지는 경우를 찾지 못해 답을 제대로 못구하고, 블로그를 참고했는데 조금 더 익숙해져야 할 것 같다.