숫자 변환하기

문제 정보

• 프로그래머스 Lv.2
• DP
• 문제 링크

풀이

필요한 최소 연산 횟수를 구하는 문제다.

dp[i]를 ‘x를 i로 변환하기 위한 최소 횟수’로 정의한다.

x부터 y까지 순서대로 순회하면서, 현재 값 i에서 도달 가능한 i + n, i * 2, i * 3의 최소 횟수를 갱신한다.

코드

import java.util.*;
 
class Solution {
    public int solution(int x, int y, int n) {
        if (x == y)
            return 0;
        
        int INF = Integer.MAX_VALUE;
        int[] dp = new int[y + 1];
        
        Arrays.fill(dp, INF);
        dp[x] = 0;
        
        for (int i = x; i <= y; i++) {
            if (dp[i] == INF) continue;
            
            if (i + n <= y)
                dp[i + n] = Math.min(dp[i + n], dp[i] + 1);
            if (i * 2 <= y)
                dp[i * 2] = Math.min(dp[i * 2], dp[i] + 1);
            if (i * 3 <= y)
                dp[i * 3] = Math.min(dp[i * 3], dp[i] + 1);
        }
        
        return dp[y] == INF ? -1 : dp[y];
    }
}