[JAVA 문제 풀이] 346. 숫자 변환하기

내가 작성한 코드

import java.util.*;

class Solution {
    public int solution(int x, int y, int n) {
        // BFS를 위한 큐: 현재 수, 연산 횟수
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {x, 0});

        // 해당 수 만들었는지 확인
        boolean[] visited = new boolean[y + 1];
        visited[x] = true;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int value = current[0]; // 현재 수
            int count = current[1]; // 연산 횟수

            if (value == y) return count;

            // 가능한 연산 결과들
            int[] nexts = {value + n, value * 2, value * 3}; // 연산 배열

            // 연산 배열 반복하며 수를 만들고 큐에 저장
            for (int next : nexts) {
                if (next <= y && !visited[next]) {
                    visited[next] = true;
                    queue.offer(new int[] {next, count + 1});
                }
            }
        }

        return -1; // 도달할 수 없는 경우
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.solution(10, 40, 5));
    }
}

다른 사람의 코드

import java.util.*;

class Solution {
    int[] dp = new int[3000003]; // dp 배열: 인덱스 번호에 도달하기 위한 최소 연산 횟수를 저장
    int INF = 1000002; // 매우 큰 값: 초기화를 위해 사용

    public int solution(int x, int y, int n) {
        Arrays.fill(dp, INF); // 모든 값 INF로 초기화 (도달 불가능한 상태로 설정)
        dp[y] = 0; // 시작 값 >> 0
        dp[x] = -1; // 시작값 x는 최종 반환을 위해 최소값으로

        // y에서부터 x까지 거꾸로 내려가며 최소 연산 수를 구하기
        for (int num = Math.max(y - n, Math.max(y / 2, y / 3)); num >= x; num--) {
            // 현재 수 num에서 시작해서 → num+n, num*2, num*3 로 갈 수 있다고 가정하고,
            // 그 지점의 dp값을 이용해서 현재 지점의 dp값을 갱신함
            dp[num] = Math.min(
                dp[num + n] + 1,
                Math.min(dp[num * 2] + 1, dp[num * 3] + 1)
            );
        }

        // dp[x]가 여전히 INF보다 크거나 같으면 도달할 수 없다는 뜻이므로 -1 반환
        return dp[x] >= INF ? -1 : dp[x];
    }
}

DP(Dynamic Programming) [동적 계획법] - stupefyee

기술정리

https://stupefyee.inblog.io/dpdynamic-programming-%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95-60377?traffic_type=internal