[pro] 프로그래머스 level2 154538 숫자 변환하기 (Java) - DP

[문제]

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

프로그래머스

 

[풀이]

dfs&bfs 풀이로 먼저 생각이 되었는데 dfs 로 풀었다가 시간초과가 났다. 그래서 완전탐색말고 더 효율적인 코드를 찾아서 dp로 풀이하게 되었다. (bfs 로 푼 정답 코드는 찾아보니 많다..)

 

dp 풀이도 단순하게 3가지 경우만 고려해주면 된다. 

dp[i] = x를 i로 변환하기 위해 필요한 최소 연산 수를 저장한다. 따라서 dp[x] = 0으로 두고 시작한다. 

1. dp[i+n] = Math.min(dp[i+n], dp[i]+1); 

2. dp[i*2] = Math.min(dp[i*2], dp[i]+1);

3. dp[i*3] = Math.min(dp[i*3], dp[i]+1);

 

이때  if(dp[i]==Integer.MAX_VALUE) continue; 코드를 넣지 않으면 몇몇 테케가 틀리는데 내 생각에 Integer.MAX_VALUE로 둔 dp 값에 오버플로우가 발생해서 답이 달라지는 경우이지 않을까 싶다.

 

[코드]

 

- dp 정답 코드

 

class Solution {
    int[] dp;
    public int solution(int x, int y, int n) {
        int answer = 0;
        // x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return
        dp = new int[y+1];
        
        for(int i=0; i<=y; i++){
            dp[i] = Integer.MAX_VALUE;
        }
        
        dp[x] = 0;
        for(int i=x; i<=y; i++){
            if(dp[i]==Integer.MAX_VALUE) continue;
            if(i+n<=y){
                dp[i+n] = Math.min(dp[i+n], dp[i]+1);
            }
            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(dp[y]==Integer.MAX_VALUE) return -1;
        return dp[y];
    }
    
    
}

 

- dfs 시간초과 코드

 

class Solution {
    int ans = Integer.MAX_VALUE;
    public int solution(int x, int y, int n) {
        int answer = 0;
        // x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return
        
        dfs(x, y, n, 0);
        if(ans==Integer.MAX_VALUE){
            return -1;
        }
        else return ans;
    
    }
    
    public void dfs(int x, int y, int n, int depth){
        if(x>y){
            return;
        }
        if(x==y){
            ans = Math.min(ans, depth);
            return;
        }
        
        dfs(x+n, y, n, depth+1);
        dfs(x*2, y, n, depth+1);
        dfs(x*3, y, n, depth+1);
        
    }
}