[해커랭크] Down to Zero II [JAVA]

문제링크 : www.hackerrank.com/challenges/down-to-zero-ii/problem

Down to Zero II | HackerRank

discussion의 풀이를 보고 괜찮은 풀이라 생각하고 나중에 다시 상기하면서 풀어본 문제다

top down 식으로 푸는 방법이 먼저 떠올랐었는데 

어떤 수의 약수를 구하는 과정을 빠르게 할 방법을 못찾았다.

bottom up 방식으로 해결했했다.

n의 값은 이전 수(1을 뺀 수)보다 최대 1이 크기 때문에 그 값과, 그 약수들 중에 가장 작은 값보다 1 큰 값 중 작은 값을 리턴한다. 

    public static int arr[];
    public static void init(){
        arr = new int[1000001];
        for(int i=0;i<=1000000;i++){
            arr[i] = -1;
        }
        arr[0] = 0; arr[1] = 1; arr[2] = 2; arr[3] = 3;
        for(int i=1;i<=1000000;i++){
            if(arr[i]== -1  || arr[i] > arr[i-1] + 1)
                arr[i] = arr[i-1] +1;
            for(int j=1;j<=i && j*i<=1000000;j++){
                if(arr[j*i] > arr[i] + 1 || arr[j*i]== -1 ){
                    arr[j*i] = arr[i] + 1;
                }
            }
        }

    }
    
    static int downToZero(int n) {
        return arr[n];
    }