숫자 변환하기

사용 알고리즘: bfs, dp

사용 언어: java

 

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;
        
        boolean[] visit = new boolean[y+1];
        
        Queue<Integer> q = new ArrayDeque<>();
        q.add(x);
        visit[x] = true;
        
        while(!q.isEmpty()) {
            int p = q.poll();
            
            if(p + n <= y && !visit[p+n]) {
                dp[p+n] = Math.min(dp[p+n], dp[p] + 1);
                q.add(p+n);
                visit[p+n] = true;
                // System.out.println(p+" "+ (p+n)+" 더함 "+dp[p+n]);
            }
            
            if(p * 2 <= y && !visit[p*2]) {
                dp[p*2] = Math.min(dp[p*2], dp[p] + 1);
                q.add(p*2);
                visit[p*2] = true;
                // System.out.println(p+" "+ (p*2)+" 2곱하기 "+dp[p*2]);
            }
            if(p * 3 <= y && !visit[p*3]) {
                dp[p*3] = Math.min(dp[p*3], dp[p] + 1);
                q.add(p*3);
                visit[p*3] = true;
                // System.out.println(p+" "+ (p+n)+" 3곱하기 "+dp[p*3]);
            }
        }
        
        return dp[y] < Integer.MAX_VALUE ? dp[y] : -1;
    }
}

 

 

메모리 초과 조심! visit 배열로 해결