P154538. 숫자 변환하기

문제

제출 코드

• 사용 알고리즘 : 자료구조, 완전탐색

연산한 결과를 큐에 넣고 반복해서 연산하여 모든 경우의 수를 헤아렸다.

연산을 해서 나온 결과가 이전에 연산된 적 없거나, 이전 연산결과보다 더 연산횟수가 적은 경우에만 큐에 현재 연산결과를 넣고 다음 연산을 수행하도록 한다.

풀이에서 사용한 dp배열은 이전 결과를 저장하면서 visit배열의 역할도 하게 된다.

import java.util.*;

class Solution {
    int[] dp;
    Queue<Integer> queue = new LinkedList<Integer>();

    void calc(int res, int now, int y){
        if(res<=y && (dp[res]==0 || dp[now]+1<dp[res])){
            dp[res] = dp[now]+1;
            queue.add(res);
        }
    }

    public int solution(int x, int y, int n) {
        if(x==y) return 0;
        dp = new int[y+1];
        queue.add(x);
        while(!queue.isEmpty()){
            int now = queue.poll();
            calc(now+n , now, y);
            calc(now*2 , now, y);
            calc(now*3 , now, y);
        }

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