[Lv.2 / Programmers / Java] 숫자 변환하기

숫자 변환하기

문제 설명

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

예시

x	y	n	result
10	40	5	2
10	40	30	1
2	5	4	-1

풀이

이 문제는 x에서 y까지 최소 연산 횟수로 도달하는 경로를 찾는 최적화 문제이다.
작은 수부터 시작해서 가능한 수들을 점차 확장하며 최솟값을 갱신해 나가는 구조이기 때문에 점화식을 기반으로 한 DP(Dynamic Programming) 방식이 적합하다고 판단했다.

i + n, i * 2, i * 3 이 3가지 경우만 생각하고 각각의 위치에서 연산을 하며 최소 연산 횟수를 갱신해줬다. 그러면 dp[y]에 갱신되서 저장된 값이 최소 연산 횟수이기 때문에 dp[y]를 출력해줬다. 단, dp[y]가 여전히 초기값이면 도달할 수 없는 것이라 판단해 -1로 반환한다.

import java.util.*;

class Solution {
    public int solution(int x, int y, int n) {
        int[] dp = new int[y + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        
        dp[x] = 0;
        for(int i=x; i<=y; i++) {
            if (dp[i] == Integer.MAX_VALUE) 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] == Integer.MAX_VALUE ? -1 : dp[y];
    }
}