[JAVA] 숫자 변환하기_DP

 

문제 : 

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

프로그래머스

 

 

접근 : 

 

* dp[x] => x 숫자를 만들기 위해서 연산되는 최소 횟수

 

  - x 부터 시작하여 y까지 2배, 3배, +n 연산을 하여 그 결과 값을 배열의 해당 인덱스에 입력한다.

   > dp[2*x] = dp[x] + 1

 

  - 만약 해당 인덱스에 값이 이미 존재한다면 현재 계산값과 해당 인덱스의 데이터 값 중 작은 값을 유지한다.

   > dp[temp] = (dp[temp] == 0) ? dp[i] + 1 : Math.min(dp[i] + 1, dp[temp]);

 

  - dp[y] 값을 출력한다. 

 

 

코드 구현 : 

 

class Solution {
    public int solution(int x, int y, int n) {
        int[] dp = new int[y + 1];
        int temp;
        int[] nums = new int[]{2, 3, n};

        if(2*x <= y) dp[2*x] = dp[x] + 1;
        if(3*x <= y) dp[3*x] = dp[x] + 1;
        if(n+x <= y) dp[n+x] = dp[x] + 1;

        for (int i = x+1 ; i <= y ; i++) {
            if (dp[i] == 0) {
                dp[i] = -1;
                continue;
            }
            for(int j = 0 ; j < nums.length ; j++){
                temp = (j == nums.length-1) ? nums[j] + i : nums[j] * i;
                if (temp > y) continue;
                dp[temp] = (dp[temp] == 0) ? dp[i] + 1 : Math.min(dp[i] + 1, dp[temp]);
            }
        }
    return dp[y];
    }
}