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

프로그래머스 숫자 변환하기 바로가기

문제 설명

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

• x에 n을 더합니다
• x에 2를 곱합니다.
• x에 3을 곱합니다.

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

접근 방식

다이나믹 프로그래밍을 이용해서 풀었다.

x 부터 y 까지 반복(i)을 도는데

현재 i 에 n 을 더하기 전의 값, 2를 곱하기 전의 값, 3을 곱하기 전의 값

이 세가지를 가지고 현재의 dp[i] 의 값을 구한다.

코드

import java.util.*;

class Solution {
    static final int maxV = 10000000;
    
    public int solution(int x, int y, int n) {
        int answer = 0;
        
        int[] dp = new int[y + 1];
        
        Arrays.fill(dp, -1);
        
        dp[x] = 0;
        
        for(int i = x; i <= y; i++){
            int val = maxV;
            
            if(i > n && dp[i - n] != -1){
                val = Math.min(val, dp[i - n] + 1);
            }
            
            if(i % 2 == 0 && dp[i / 2] != -1){
                val = Math.min(val, dp[i / 2] + 1);
            }
 
            if(i % 3 == 0 && dp[i / 3] != -1){
                val = Math.min(val, dp[i / 3] + 1);
            }           
            
            if(val != maxV) dp[i] = val;
            
        }
        
        answer = dp[y];
        
        return answer;
    }
}

Disscussion

비교적 접근이 쉬운 DP문제였다.