[프로그래머스/Lv. 2] 숫자 변환하기 (JAVA)

🔺 문제

프로그래머스

 

 

🔺 코드

import java.util.*;
 
class Solution {
    static int MAX = 987654321;
    
    public int solution(int x, int y, int n) {
        int answer = 0;
        
        int[] dp = new int[y + 1];
       Arrays.fill(dp, MAX); // 충분히 큰 값으로 초기화
        dp[x] = 0;
        
        for(int i = x ; i <= y ; i++) {
            if(i * 3 <= y) {
                dp[i * 3] = Math.min(dp[i * 3], dp[i] + 1);
            }
            if(i * 2 <= y) {
                dp[i * 2] = Math.min(dp[i * 2], dp[i] + 1);
            }
            if(i + n <= y) {
                dp[i + n] = Math.min(dp[i + n], dp[i] + 1);
            }
        }
        
        return dp[y] == MAX ? -1 : dp[y];
    }
}

 

 

🧩 해결 아이디어

• DP

- dp[i] : i를 만들기 위해 필요한 최소 연산 횟수

└ dp[x]를 제외한 배열의 모든 값은 충분히 큰 값으로 초기화

└ 현재 값에서 3 곱했을 때 y보다 작거나 같다면 dp[i * 3] = Math.min(dp[i * 3], dp[i] + 1);

└ 현재 값에서 2 곱했을 때 y보다 작거나 같다면 dp[i * 2] = Math.min(dp[i * 2], dp[i] + 1);

└ 현재 값에서 n 더했을 때 y보다 작거나 같다면 dp[i + n] = Math.min(dp[i + n], dp[i] + 1);

 

---

💬 느낀 점

이 정도 DP문제는 이제 풀 수 있고 재밌다....

내 생각보다 DP 푸는 감이 아주 조금은 늘었을지도......

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ DP 배열 초기화할 때 Integer.MAX_VALUE로 설정하고도 오버플로우 발생하는 경우를 막기 위한 코드를 넣으셨다.

=> for문 안에서 if(dp[i] == Integer.MAX_VALUE) continue; 추가

[pro] 프로그래머스 level2 154538 숫자 변환하기 (Java) - DP