[프로그래머스] 숫자 변환하기(154538)

1. 문제 풀이 아이디어

• 다이나믹 프로그래밍을 활용하면 문제를 해결할 수 있다.

2. 나의 정답 코드

class Solution {
    public int solution(int x, int y, int n) {
        int[] dp = new int[y + 1];
        dp[x] = 1;
        for (int i = x + 1; i <= y; i++) {
            int result = Integer.MAX_VALUE;
            if (i - n > 0 && dp[i - n] > 0)
                result = Math.min(dp[i - n] + 1, result);
            if (i % 2 == 0 && dp[i / 2] > 0)
                result = Math.min(dp[i / 2] + 1, result);
            if (i % 3 == 0 && dp[i / 3] > 0)
                result = Math.min(dp[i / 3] + 1, result);
            if (result != Integer.MAX_VALUE)
                dp[i] = result;
        }
        return dp[y] > 0 ? dp[y] - 1 : -1;
    }
}

3. 정리

• dp 배열을 크기 y + 1로 정의하고, dp[x]를 1로 초기화한다.

• x + 1부터 y까지 반복문을 실행한다.
• result를 Integer.MAX_VALUE로 초기화한다.
• i - n, i / 2, i / 3의 조건을 확인하여 최소값을 result에 저장한다.
• result가 Integer.MAX_VALUE가 아니라면 dp[i]에 저장한다.

• 반복문이 종료되면 dp[y]가 0보다 크면 값을 1 감소시켜 반환하고, 그렇지 않으면 1을 반환한다.