[프로그래머스] - 숫자 변환하기 JAVA 풀이

프로그래머스 - 숫자 변환하기 JAVA 풀이

문제 설명

자연수x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

• x에 n을 더합니다
• x에 2를 곱합니다.
• x에 3을 곱합니다.
  자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

---

제한사항

• 1 ≤ x ≤ y ≤ 1,000,000
• 1 ≤ n < y

---

입출력 예

입출력 예

---

아이디어

• 브루트포스로는 시간초과
• bfs로 해결이 가능하지만 dp가 가장 적절한 해법인듯 하다
• 각 계산식 경우의 수 마다 비교해가면서 dp 배열 만들고 변환 불가처리만 주의하자

---

JAVA 풀이

class Solution {
    public int solution(int x, int y, int n) {
        int[] dp = new int[y + 1];
        for (int i = x; i < y + 1; i++) {
            if (i != x && dp[i] == 0) {
                dp[i] = -1;
                continue;
            }
            if (i * 2 <= y) {
                if (dp[i * 2] == 0) {
                    dp[i * 2] = dp[i] + 1;
                } else {
                    dp[i * 2] = Math.min(dp[i] + 1, dp[i * 2]);
                }
            }
            if (i * 3 <= y) {
                if (dp[i * 3] == 0) {
                    dp[i * 3] = dp[i] + 1;
                } else {
                    dp[i * 3] = Math.min(dp[i] + 1, dp[i * 3]);
                }
            }
            if (i + n <= y) {
                if (dp[i + n] == 0) {
                    dp[i + n] = dp[i] + 1;
                } else {
                    dp[i + n] = Math.min(dp[i] + 1, dp[i + n]);
                }
            }
        }
        return dp[y];
    }

}