[JAVA] 백준 다이나믹 프로그래밍 연습문제 - BOJ 1463

주어진 수에 /3, /2, -1을 사용해 최소횟수로 1을 만드는 프로그램

 

탑다운(재귀)방식으로 작성.

메모리제이션을 위한 배열 D[]를 만든다.

 

주어진 수를 쪼개어 작은 수(x-1, x/2, x/3)로 만들고,

작은 수들에 대해 세 가지 방법 중 최소횟수인 방법을 찾아 배열에 저장한다.

 

x=1일 때, 재귀에서 빠져나온다.

 

import java.util.Scanner;

public class BOJ1463 {

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int x=sc.nextInt();
        int[] D=new int[1000001];
        System.out.println(operate(x, D));
    }

    static int operate(int x, int[] D){
        if(x==1) return 0;
        if(D[x]>0) return D[x];

        D[x]=operate(x-1,D)+1;

        if(x%2==0){
            int tmp=operate(x/2,D)+1;
            if(D[x]>tmp){
                D[x]=tmp;
            }
        }
        if(x%3 ==0){
            int tmp=operate(x/3,D)+1;
            if(D[x]>tmp){
                D[x]=tmp;
            }
        }
        return D[x];
    }
}