[프로그래머스] 숫자 변환하기 ⭐

📚 문제 설명

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

🔎 입출력 예

💻 코드

import java.math.*;
class Solution {
    public int solution(int x, int y, int n) {
        int answer = 0;
        int[] dp = new int[y+1];
        
        for(int i=x; i<=y; i++) {
            // 변환할수 없는 값이면 -1;
            if(i!=x && dp[i] == 0) {
                dp[i] = -1;
                continue;
            }
            
            // x에 n을 더한 값
            if(i+n <= y) {
                dp[i+n] = (dp[i+n] == 0) ? dp[i] + 1 : Math.min(dp[i] + 1, dp[i+n]);
            }
            
            // x에 2를 곱한 값
            if(i*2 <= y) {
                dp[i*2] = (dp[i*2] == 0) ? dp[i] + 1 : Math.min(dp[i] + 1, dp[i*2]);
            }
            
            // x에 3을 곱한 값
            if(i*3 <= y) {
                dp[i*3] = (dp[i*3] == 0) ? dp[i] + 1 : Math.min(dp[i] + 1, dp[i*3]);
            }
        }

        return dp[y];
    }
}

📖 Solution

문제를 읽고 이문제는 bfs로 푸는게 좋을까 dp로 푸는게 좋을까 고민을 했다. 사실 아직도 두개 다 익숙하지 않다... 문제를 풀때마다 어렵고 새로워 😥

dp 방식이 더 간단할거 같아서 참고해 풀기로 했다.

단순하게 3가지 방식만 고려해주면된다.
1. x에 n을 더합니다.
2. x에 2를 곱합니다.
3. x에 3을 곱합니다.

먼저 y값에 맞게 dp 배열을 생성한후 반복문을 사용하여 x부터 y까지 3가지 방식을 수행하면 된다.
이때 3가지 방식으로 변환할 수 없는 값이면 -1을 넣어주고 변환 할 수 있는 값이면 이미 있는 값(dp[변환하는 값]) 과 새로운 값(dp[i]+1) 중에 최소값을 선택하면된다.

이러한 방식으로 y까지 반복문이 돌면 y가 정답이 된다.