백준알고리즘 1463번 1로만들기

백준알고리즘

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

Top-down 방식이 아닌 bottom-up 방식으로 코딩했다.

package test11;

import java.util.Scanner;

public class Test {
    public static int[] memoArray;
    public static int count;
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in); 
        count = Integer.parseInt(scan.nextLine().trim());
        memoArray = new int[count + 1];
        
        for(int i = 0; i < memoArray.length; i++) {
            if(i == 1) {
                memoArray[i] = 0;
                
                continue;
            }
            memoArray[i] = i;
        }
        calculate(count);
    }
    
    public static void calculate(int data) {
        for(int i = 1; i < memoArray.length; i++) {
            int val = i;
            
            if(val + 1 <= count) {
                int temp = memoArray[val] + 1;
                if(memoArray[val + 1] > temp) {
                    memoArray[val + 1] = temp;
                }
            }
            
            if(i * 2 <= count) {
                int temp = memoArray[val] + 1;
                
                if(memoArray[val * 2] > temp) {
                    memoArray[val * 2] = temp;
                }
            }
            
            if(i * 3 <= count) {
                int temp = memoArray[val] + 1;
                
                if(memoArray[val * 3] > temp) {
                    memoArray[val * 3] = temp;
                }
            }
        }
        
        System.out.println(memoArray[memoArray.length - 1]);
    }
}