[자바] 숫자변환하기

https://school.programmers.co.kr/learn/courses/30/lessons/154538

프로그래머스

 

완전탐색으로, 목표값 도달이 가능한지 찾는 문제이다.

완탐으로 dfs를 많이써서 풀었었는데, dfs로 풀면 재귀호출 오류가 난다.

 

bfs로 풀고자 했는데, 어떻게 풀어야할지 모르겠었다.

그래서 문제를 최대 배열을 만들어 놓고, 중복되지 않는 값(arr[x]==0)이고, x가 범위를 벋어나지 않는다면,

배열의 x+n/ x*2 / x*3인덱스에 x를 거쳐온 값(cnt)+1씩한 값을 넣어주면서, 연산횟수를 세려갔다. 

이렇게 연산횟수를 저장하면서 그래프를 이으면서 문제를 풀었다.

import java.util.*;
class Solution {
    public static int[] arr;
    public int solution(int x, int y, int n) {
        arr = new int[1000001]; //x에서 y까지 가는 최단거리(하나하나 배열씩 체크)
        bfs(x,y,n);
        if (arr[y]==0) {
            arr[y]=-1;
        }
        return arr[y];
    }
    
    public static void bfs(int i, int j, int n) {
        Queue<Integer> q = new LinkedList<>(); 
        //bfs로 풀려면, x에서 y로 가는 최단거리의 개념으로 구해야함
        q.add(i);
        
        while (!q.isEmpty()) {
            int x = q.poll();
            if( x*3>=0 && x*3<=1000000 && arr[x*3]==0) {
                q.add(x*3);
                arr[x*3]= arr[x]+1;
            }
            if( x*2>=0 && x*2<=1000000 && arr[x*2]==0) {
                q.add(x*2);
                arr[x*2]= arr[x]+1;
            }
            if( x+n>=0 && x+n<=1000000 && arr[x+n]==0) {
                q.add(x+n);
                arr[x+n]= arr[x]+1;
            }
        }
        
    }
}

 

<다른 풀이>

dp를 이용해서 x부터 y까지 늘려가는동안 dp배열에 그 숫자가 가능한 경우의 수를 넣는다.

다만, 최소의 경우의 수를 구해야하기 때문에, dp[i+n]과 dp[i]+1 중 작은 값을 dp배열에 저장하면서 값을 찾는다.

import java.util.*;  
  
class Solution {  
    public int solution(int x, int y, int n) {  
        int[] dp = new int[y + 1];  
        Arrays.fill(dp, -1);  
        dp[x] = 0;  
        for (int i = x; i <= y; i++) {  
            if (dp[i] == -1) continue;  
            if (i + n <= y) {  
                if (dp[i + n] == -1) {  
                    dp[i + n] = dp[i] + 1;  
                } else {  
                    dp[i + n] = Math.min(dp[i + n], dp[i] + 1);  
                }  
            }  
            if (i * 2 <= y) {  
                if (dp[i * 2] == -1) {  
                    dp[i * 2] = dp[i] + 1;  
                } else {  
                    dp[i * 2] = Math.min(dp[i * 2], dp[i] + 1);  
                }  
            }  
            if (i * 3 <= y) {  
                if (dp[i * 3] == -1) {  
                    dp[i * 3] = dp[i] + 1;  
                } else {  
                    dp[i * 3] = Math.min(dp[i * 3], dp[i] + 1);  
                }  
            }  
        }  
        return dp[y];  
    }  
}