[프로그래머스] 154538번 : 숫자 변환하기

ghltjd369·2023년 9월 16일

DP 프로그래머스

📌 출처

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	y	n	result
10	40	5	2
10	40	30	1
2	5	4	-1

🖨 입출력 예 설명

입출력 예 #1
x에 2를 2번 곱하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #2
x에 n인 30을 1번 더하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #3
x를 y로 변환할 수 없기 때문에 -1을 return합니다.

💻 내 코드

1. 리스트를 사용하여 구현

class Solution {
    private static final int MAX = Integer.MAX_VALUE;

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

        int[] dp = new int[y + 1];

        for (int i = x + 1; i < y + 1; i++) {
            int a = MAX, b = MAX, c = MAX, d;

            if (isDivided(i, 2) && aboveX(x, i / 2)) a = dp[i / 2];
            if (isDivided(i, 3) && aboveX(x, i / 3)) b = dp[i / 3];
            if (aboveX(x, i - n)) c = dp[i - n];

            // 숫자 i를 만들기 위한 최소 방법을 찾음
            d = Math.min(a, b);
            d = Math.min(d, c);

            // 만들 수 있으면 d+1 저장
            // 만들 수 없다면 MAX 저장
            dp[i] = (d < MAX) ? d + 1 : MAX;
        }

        // y를 만들 수 없다면 -1 반환
        answer = (dp[y] < MAX) ? dp[y] : -1;

        return answer;
    }

    // x 보다 작은 위치의 값을 비교하지 않게 함
    private static boolean aboveX(int x, int num) {
        return (num >= x);
    }

    //  (i / 2), (i / 3)의 연산 결과가 자연수인지 확인함
    private static boolean isDivided(int num, int divide) {
        return (num / divide > 0 && num % divide == 0);
    }
}

✏ 설명

오랜만에 풀어보는 dp 문제..

총 3가지의 연산이 가능하다

푸는 방법은 다음과 같다.

x부터 y까지 최소 방법을 갱신해가며 나아간다.
현재 위치에서 (i/2), (i/3), (i-n)의 위치에 있는 값을 가져와 비교한다.

말로는 이해하기 어려우니, 그림으로 설명해보자
x=10, y=25, n=5인 경우를 생각해보자.

우선 y의 값까지 배열을 만든다.

x는 10이고, 11부터 25까지 1씩 증가시키며 해당 숫자를 만들 수 있는 최소 방법을 찾아간다.
우선, 10을 만드는 방법은 자기 자신이므로 0이다.

11을 만드는 방법은 다음과 같다.

11은 2의 배수가 아니므로 2를 곱해서 만들 수 없다.
11은 3의 배수가 아니므로 3을 곱해서 만들 수 없다.
11 - 5 = 6

11을 만들 수 있는 방법은 6에서 5를 더하는 방법 뿐인데 x보다 작은 값이기 때문에 제외시킨다.
11~14까지 동일한 이유로 만들 수 없다.
만들 수 없는 수는 MAX로 표시한다.

15를 만들 수 있는 방법은 다음과 같다.

15는 2의 배수가 아니므로 만들 수 없다.
15 / 3 = 5
15 - 10 = 10

15는 10+5로 만들 수 있다.
따라서 한 가지의 방법으로 만들 수 있으므로 그 최소값을 저장한다.

16~19도 만들 수 없다.

20을 만들 수 있는 방법은 (i / 2)와 (i - n)이다.
(i / 2)의 값은 10이고, 배열 10에 저장된 값인 0에서 1을 더한 값인 1이 20을 만들 수 있는 최소이다.
(i - n)의 값은 15이고, 배열 15에 저장된 값인 1에서 1을 더한 값인 2가 20을 만들 수 있는 최소이다.

두 경우를 비교했을 때 (i / 2)인 10에서 만드는 것이 최소이므로 1이 최소가 된다.