프로그래머스 - 숫자 변환하기(Java)

동적 프로그래밍(dp) 문제입니다.

 

x, y, n의 값이 주어집니다.

세 가지 연산을 통해 y를 만드는 최소 방법을 구해야합니다.

 

세 가지 연산은 다음과 같습니다.

• x * 2
• x * 3
• x + n

이는 x부터 y까지 최소 방법을 갱신해 나아가며 나아가되,

현재 위치에서 (i / 2), (i / 3), (i - n)의 위치에 있는 값을 가져와 비교를 하면 됩니다.

 

말로는 이해하기 힘들 수 있으니 x = 10, y = 25, n = 5일 때를 그림으로 나타내 보겠습니다.

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

x의 값은 10이기 때문에, 11 ~ 25 까지 1씩 증가시켜

해당 숫자를 만드는 최소 방법을 배열에 저장시킵니다.

 

10을 만드는 방법은 x 자신이므로 0입니다.

11의 세 가지 연산은 다음과 같습니다.

• 11 / 2 = 5
• 11 / 3 = 3 
• 11 - 5 = 6 

5, 3, 6은 모두 x 보다 작은 값이기 때문에 연산에서 제외시켜야 합니다.

 

11 ~ 14 까지 연산의 결과는 만들 수 없다 입니다.

만들 수 없다는 표식은 MAX라고 하겠습니다.

15의 세 가지 연산은 다음과 같습니다.

• 15 / 2 = 7
• 15 / 3 = 5
• 15 - 5 = 10

15를 만들 수 있는 방법이 나타났습니다.

방법은 (i - n)입니다.

15는 한 가지 방법으로 만들 수 있으니 그 최소를 저장합니다.

 

위와 같은 방법으로 16 ~ 19는 만들 수 없습니다.

 

20의 세 가지 연산은 다음과 같습니다.

• 20 / 2 = 10
• 20 / 3 = 6
• 20 - 5 = 15

20을 만들 수 있는 방법은 (i / 2)와 (i - n) 입니다.

여기서 이 두 가지를 비교해야 합니다.

첫째, 

(i / 2)의 값은 10입니다. 배열 10에 저장된 값인 0에서 1을 더한 값이 20을 만들 수 있는 최소 입니다.

둘째,

(i - n)의 값은 15입니다. 배열 15에 저장된 값이 1에서 1을 더한 값이 20을 만들 수 있는 최소 입니다.

즉,

(0 + 1) 과 (1 + 1)의 값을 비교하여 최소인 1을 20 위치에 저장하면 됩니다.

 

감이 오셨나요?

그러면 21 ~ 25의 값은 무엇일까요?

 

네,

21 ~ 24는 만들 수 없습니다.

25는 (i - n)에 의해 2가 됩니다.

 

[구현 코드]

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);
    }
}