[Programmers] 154538번 - 숫자 변환하기 [Java][C++]

문제 링크

---

1. 문제 풀이

다이나믹 프로그래밍을 활용해도 되고 BFS를 활용해도 해결할 수 있다.

다이나믹 프로그래밍의 경우 dp 테이블에서 인덱스를 숫자 $i$, 값을 $x$ 에서 해당 숫자로 변환하는데 필요한 최소 쵯수를 기록하면 된다. 초기 무한대로 초기화한 후 $dp[x] = 0$ 으로 초기화를 해준다. 이후 $x$ 부터 $n$ 을 더한 수, $2$ 를 곱한 수, $3$ 을 곱한 수는 1번만 변환하면 되므로 기존의 변환하는데 필요한 최소 횟수와 현재 수에서 1번만 변환하면 되므로 둘 중 최솟값을 기록해주면 된다. 모든 변환이 수가 커지는 방향이므로 다음 수로 한칸씩 이동하며 해당 과정을 반복하면 된다.

BFS의 경우 일반적인 최단거리를 구하는 BFS를 활용해 방문 체크를 하며 구해주면 된다.

---

2. 코드

1. BFS [Java]

import java.util.*;

class Solution {
    public int solution(int x, int y, int n) {
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(x);

        boolean[] visited = new boolean[y * 3];
        visited[x] = true;

        int dist = 0;

        while (!q.isEmpty()) {
            int size = q.size();

            while (size-- > 0) {
                int node = q.poll();
                if (node == y) return dist;

                if (node + n <= y && !visited[node + n]) {
                    q.add(node + n);
                    visited[node + n] = true;
                }

                if (node * 2 <= y && !visited[node * 2]) {
                    q.add(node * 2);
                    visited[node * 2] = true;
                }

                if (node * 3 <= y && !visited[node * 3]) {
                    q.add(node * 3);
                    visited[node * 3] = true;
                }
            }

            dist++;
        }

        return -1;
    }
}

2. 다이나믹 프로그래밍 [Java]

import java.util.*;

class Solution {

    static final int MAX = 1_000_000;

    public int solution(int x, int y, int n) {
        int[] dp = new int[1 + y * 3];
        Arrays.fill(dp, MAX);
        dp[x] = 0;

        for (int i = x; i <= y; i++) {
            dp[i + n] = Math.min(dp[i + n], dp[i] + 1);
            dp[i * 2] = Math.min(dp[i * 2], dp[i] + 1);
            dp[i * 3] = Math.min(dp[i * 3], dp[i] + 1);
        }

        return dp[y] == MAX ? -1 : dp[y];
    }
}

3. BFS [C++]

#include <queue>
#include <string>
#include <vector>

using namespace std;

int solution(int x, int y, int n) {
    queue<int> q;
    q.push(x);

    vector<bool> visited(y * 3);
    visited[x] = true;

    int dist = 0;

    while (!q.empty()) {
        int sz = q.size();

        while (sz--) {
            int node = q.front();
            q.pop();

            if (node == y) return dist;

            if (node + n <= y && !visited[node + n]) {
                q.push(node + n);
                visited[node + n] = true;
            }

            if (node * 2 <= y && !visited[node * 2]) {
                q.push(node * 2);
                visited[node * 2] = true;
            }

            if (node * 3 <= y && !visited[node * 3]) {
                q.push(node * 3);
                visited[node * 3] = true;
            }
        }

        dist++;
    }

    return -1;
}

4. 다이나믹 프로그래밍 [C++]

#include <algorithm>
#include <string>
#include <vector>

using namespace std;

constexpr int MAX = 1000000;

int solution(int x, int y, int n) {
    vector<int> dp(1 + y * 3, MAX);
    dp[x] = 0;

    for (int i = x; i <= y; i++) {
        dp[i + n] = min(dp[i + n], dp[i] + 1);
        dp[i * 2] = min(dp[i * 2], dp[i] + 1);
        dp[i * 3] = min(dp[i * 3], dp[i] + 1);
    }

    return dp[y] == MAX ? -1 : dp[y];
}

---