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

문제 링크

---

1. 아이디어

자연수 x를 y로 변환하는 최소 연산 횟수를 구하는 문제로 bfs를 활용해도 되고 dp를 활용해도 된다.

bfs의 경우 노드를 연산 결과인 숫자로 정의했을 때 x에서 출발해서 y를 발견하는 최단 거리가 최소 연산 횟수가 된다. 따라서 x인 경우 거리를 0으로 두고 x + n, x * 2, x * 3을 x에 연결된 노드로 보고 다시 각 값에 대해 연산을 수행하는 과정을 반복해서 y가 나올 때 거리를 반환하는 방식으로 해결했다.

dp의 경우 dp[i]를 i를 만드는데 필요한 최소 연산 횟수로 정의하면 된다. 이러면 i에서 한번의 연산을 하면 i + n, i * 2, i * 3을 만들 수 있으므로 아래와 같은 점화식을 세울 수 있다.

\[dp[i + n] = \min(dp[i + n], dp[i] + 1)\\ dp[i \times 2] = \min(dp[i \times 2], dp[i] + 1)\\ dp[i \times 3] = \min(dp[i \times 3], dp[i] + 1)\\\]

구현에서는 i를 x부터 y까지 순회하며 dp 테이블을 갱신하면 되는데 3가지 연산 모두 값을 증가시키는 연산이어서 dp[i]는 해당 값으로 i보다 작은 수에서 온 모든 연산을 고려하고 있다.

---

2. 복잡도

1. bfs

시간복잡도	공간복잡도
$O(Y)$	$O(Y)$

$Y$ = y(도달 목표값)

2. dp

시간복잡도	공간복잡도
$O(Y)$	$O(Y)$

$Y$ = y(도달 목표값)

---

3. 코드

1. bfs [Java][C++]

import java.util.*;

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

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

        while (!q.isEmpty()) {
            int cur = q.poll();
            if (cur == y) return dist[cur];

            if (cur + n <= y && dist[cur + n] == -1) {
                q.offer(cur + n);
                dist[cur + n] = dist[cur] + 1;
            }

            if (cur * 2 <= y && dist[cur * 2] == -1) {
                q.offer(cur * 2);
                dist[cur * 2] = dist[cur] + 1;
            }

            if (cur * 3 <= y && dist[cur * 3] == -1) {
                q.offer(cur * 3);
                dist[cur * 3] = dist[cur] + 1;
            }
        }

        return -1;
    }
}

#include <queue>
#include <vector>

using namespace std;

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

    vector<int> dist(1 + y, -1);
    dist[x] = 0;

    while (!q.empty()) {
        int cur = q.front();
        q.pop();

        if (cur == y) return dist[cur];

        if (cur + n <= y && dist[cur + n] == -1) {
            q.push(cur + n);
            dist[cur + n] = dist[cur] + 1;
        }

        if (cur * 2 <= y && dist[cur * 2] == -1) {
            q.push(cur * 2);
            dist[cur * 2] = dist[cur] + 1;
        }

        if (cur * 3 <= y && dist[cur * 3] == -1) {
            q.push(cur * 3);
            dist[cur * 3] = dist[cur] + 1;
        }
    }

    return -1;
}

2. dp [Java][C++]

dp 테이블에서 i + n, i * 2, i * 3 같은 다음 연산이 y를 넘어갈 수 있으므로 배열의 크기를 1 + y * 3까지 넉넉하게 세팅해줬다.

import java.util.*;

class Solution {

    static 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];
    }
}

#include <algorithm>
#include <vector>

using namespace std;

const int MAX = 1'000'000;

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

---