[프로그래머스] 숫자 변환하기 (Java/Python)

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

문제요약

---

아래와 같은 세 가지 연산만으로 자연수 x를 y로 변환하려 한다.

• x에 n을 더한다.
• x에 2를 곱한다.
• x에 3을 곱한다.

자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return 하고 만약 x를 y로 변환할 수 없는 경우 -1을 return 하는 함수를 만들어 보자.

제한사항

---

• 1 ≤ x ≤ y ≤ 1000000
• 1 ≤ n < y

입출력 예

---

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

문제풀이

---

해당 문제를 보고 가장 먼저 떠오른 풀이는 트리의 leaf node (말단 노드)를 찾는 방식이였다. 각 노드가 + n, * 2, * 3을 의미하는 세 자식 노드를 가지면서, y값에 도달하면 트리의 최소 레벨을 찾으면 되는 식이였다. 하지만 y는 최대 백만이고, 그에비해 n이 매우 작다면, 모든 트리를 탐색하는데 오래걸리면서 시간초과가 될 것 같았다.
따라서 dynamic programing을 사용하여, x와 y 사이의 모든 수에 대해서 도달하는 데 필요한 최소 연산 횟수를 하나의 배열에 저장해두고, y번째에 있는 원소값을 리턴하게 하였다. 배열은 -1로 초기화해두고, x번째 원소만 0으로 지정해둔다.

코드

---

Java

public class TransNumber {
    public int solution(int x, int y, int n) {
        int[] dp = new int[y + 1];

        Arrays.fill(dp, -1);
        dp[x] = 0;
        for (int i = x; i <= y; i++) {
            if (dp[i] == -1) continue;
            save(i, y, i + n, dp);
            save(i, y, i * 2, dp);
            save(i, y, i * 3, dp);
        }
        return dp[y];
    }

    private void save(int origin, int target, int num, int[] dp) {
        if (num <= target) {
            if (dp[num] == -1) {
                dp[num] = dp[origin] + 1;
            } else {
                dp[num] = Math.min(dp[origin] + 1, dp[num]);
            }
        }
    }
}

Python

def solution(x, y, n):
    dp = [-1 for _ in range(y + 1)]
    dp[x] = 0

    for i in range(x, y):
        if dp[i] == -1:
            continue

        if i + n <= y:
            dp[i + n] = dp[i] + 1 if dp[i + n] == -1 else min(dp[i + n], dp[i] + 1)

        if i * 2 <= y:
            dp[i * 2] = dp[i] + 1 if dp[i * 2] == -1 else min(dp[i * 2], dp[i] + 1)

        if i * 3 <= y:
            dp[i * 3] = dp[i] + 1 if dp[i * 3] == -1 else min(dp[i * 3], dp[i] + 1)

    return dp[y]