[동적프로그래밍] 프로그래머스 숫자 변환하기 level2 자바 Java

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/154538

프로그래머스

 

문제 설명

자연수 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

풀이

더하기 연산을 사용한경우, 2를 곱한 경우, 3을 곱한 경우로 나눠서 동적프로그래밍 하면 된다.

 

코드

class Solution {
    private static int[] dp;
    public static final int MAX_VALUE = Integer.MAX_VALUE;

    public int solution(int x, int y, int n) {
        dp = new int[y + 1];
        for (int i = x + 1; i <= y; i++) {
            int a = i - n >= x ? dp[i - n] : MAX_VALUE; //더하기 연산 사용한 경우
            int b = i / 2 >= x && i % 2 == 0 ? dp[i / 2] : MAX_VALUE; // 2를 곱한 경우
            int c = i / 3 >= x && i % 3 == 0 ? dp[i / 3] : MAX_VALUE; //3을 곱한경우

            int d = Math.min(a, b);
            d = Math.min(d, c);

            dp[i] = (d < MAX_VALUE) ? d + 1 : MAX_VALUE;
        }
        return dp[y] < MAX_VALUE ? dp[y] : -1;
    }
}