[프로그래머스/JAVA 자바] 숫자 변환하기

 

프로그래머스

 

문제풀이

1. 재귀함수로 해결하려 했으나 일부 테스트케이스 시간초과 및 런타임에러 ( 실패 )

2. dp로 해결.

3. int[] dp 사이즈를 y+1 의 크기로 생성 후 dp [ i ] 에 최소 연산 수를 저장

4. dp[x] = 0 으로 초기화하고 반복문 시작

 

 

나의풀이 ( 코드 )

class Solution {
    public int solution(int x, int y, int n) {
        
        int answer = -1;

        int[] dp = new int[y + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i] = 1000001;
        }
        dp[x] = 0;

        for (int i = x; i <= y; i++) {
            if (dp[x] == 1000001) {
                continue;
            }
            if (i + n <= y) {
                dp[i + n] = Math.min(dp[i + n], dp[i] + 1);
            }
            if (i * 2 <= y) {
                dp[i * 2] = Math.min(dp[i * 2], dp[i] + 1);
            }
            if (i * 3 <= y) {
                dp[i * 3] = Math.min(dp[i * 3], dp[i] + 1);
            }
        }

        if (dp[y] != 1000001) {
            answer = dp[y];
        }
        return answer;
    }
}

 

 

실패한 풀이 ( 코드 )

class Solution {
    
    static int min = 1000001;
    
    static int sum;
    
    public int solution(int x, int y, int n) {
        int answer = -1;
        
        sum = n;
        dfs(x, y, 0);

        if (min != 1000001) {
            answer = min;
        }
        
        return answer;
    }
    
    static void dfs(int x, int y, int count) {

        if (x == y && min > count) {
            min = count;
            return;
        } else if (x > y) {
            return;
        }

        dfs(x * 2, y, count + 1);
        dfs(x * 3, y, count + 1);
        dfs(x + sum, y, count + 1);
    }
    
}