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

https://school.programmers.co.kr/learn/courses/30/lessons/154538

문제 설명

자연수 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 = 10, y = 60, n = 5인 경우 x가 y와 같아지는 경우는 x가 30일 때 2를 곱하는 경우, x가 20일 때 3을 곱하는 경우, x가 55일 때 5를 더하는 경우 총 3가지 경우가 있다.

따라서 보텀업 다이나믹 프로그래밍 방식을 사용해 x를 처음 연산한 값들을 배열에 저장해가며 x가 y가 되기 위한 직전 연산 y / 2, y / 3, y - n의 연산 횟수 중 최솟값에 연산 횟수 1을 더해주면 된다.

풀이

import java.util.Arrays;

class Solution {
    public int solution(int x, int y, int n) {
        int answer = 0;

        int[] dp = new int[y + 1];
        Arrays.fill(dp, 1000001);
        
        dp[x] = 0;

        for (int i = x + 1; i <= y; i++) {
            if (i % 2 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            }
            if (i % 3 == 0) {
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
            }
            if (i - n >= 0) {
                dp[i] = Math.min(dp[i], dp[i - n] + 1);
            }
        }
        answer = dp[y] < 1000001 ? dp[y] : -1;
        return answer;
    }
}

결과