[오늘의 문제] 숫자 변환하기

출처: https://school.programmers.co.kr/learn/courses/30/lessons/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합니다.

사실 내가 현업에서도 큐나 BFS를 써본적이 없었고,

접근자체가 안되는 문제였다.

그냥 배워가는 차원으로 써보겠다.

방문 배열 visited[] 활용
import java.util.*;

class Solution {
public int solution(int x, int y, int n) {
int answer = -1;
Queue<int[]> queue = new ArrayDeque<>();
boolean[] visited = new boolean[y+1];
queue.add(new int[] {x,0});
while(!queue.isEmpty()) {
int[] cur = queue.poll();
visited[cur[0]] = true;
if(cur[0] == y) {
answer = cur[1];
break;
}
if(cur[0]2 <= y && !visited[cur[0]2]) {
queue.add(new int[] {cur[0]2, cur[1]+1});
}
if(cur[0]3 <= y && !visited[cur[0]3]) {
queue.add(new int[] {cur[0]3, cur[1]+1});
}
if(cur[0]+n <= y && !visited[cur[0]+n]) {
queue.add(new int[] {cur[0]+n, cur[1]+1});
}
}
return answer;
}
}

dp 사용
import java.util.*;

class Solution {
public int solution(int x, int y, int n) {
int[] dp = new int[y+1];
Arrays.fill(dp, Integer.MAX_VALUE);

    dp[x] = 0;
    for(int i=x; i<=y; i++) {
        if(dp[i] == Integer.MAX_VALUE) continue;
        // 아직 도달하지 않은 숫자는 건너뛴다.
        if(i * 2 <= y) {
            dp[i*2] = Math.min(dp[i*2],dp[i]+1);
        }
        if(i * 3 <= y) {
            dp[i*3] = Math.min(dp[i*3],dp[i]+1);
        }
        if(i + n <= y) {
            dp[i+n] = Math.min(dp[i+n],dp[i]+1);
        }
    }
    return dp[y] == Integer.MAX_VALUE ? -1 : dp[y];
}

}