[Java] 프로그래머스 Lv2. 숫자 변환하기

모법 답안

import java.util.*;

class Solution {

    int[] dp = new int[3000003];
    int INF = 1000002;

    public int solution(int x, int y, int n) {
        int answer = 0;
        Arrays.fill(dp, INF);
        dp[x] = -1;
        dp[y] = 0;
        for(int num = Math.max(y - n, Math.max(y / 2, y / 3)); num >= x; num--){
            dp[num] = Math.min(dp[num + n] + 1, Math.min(dp[num * 2] + 1, dp[num * 3] + 1));
        }
        return dp[x] >= INF ? -1 : dp[x];
    }
}

내 풀이(실패, 시간초과, 런타임 에러 - 2023.4.8)

import java.util.Arrays;
class Solution {
    public int solution(int x, int y, int n) {
        int[] dp =new int[y+1];
        if(x+n<=y) dp[x+n]=1;
        if(x*2<=y) dp[x*2]=1;
        if(x*3<=y) dp[x*3]=1;
            
        if(dp[y]>0){
            return dp[y];
        }
        dfs(y, x, n, dp);
        int answer = dp[y];
        
        if(answer==0){
            return -1;
        }
        return answer;
    }
    
    private void dfs(int idx, int x, int n, int[] dp){
        if(idx<=x+n||idx<=x*2||idx<=x*3){
            return;
        }
        
        if(idx%3==0){
            if(dp[idx/3]>0){
                dp[idx]+=dp[idx/3];
            }else{           
                dfs(idx/3,x,n,dp);
                dp[idx]+=dp[idx/3];
                }
            }
        if(idx%2==0){
            if(dp[idx/2]>0){
                dp[idx]+=dp[idx/2];
            }else{           
                dfs(idx/2,x,n,dp);
                dp[idx]+=dp[idx/2];
            }
        }
        if(dp[idx-n]>0){
            dp[idx]+=dp[idx-n];
        }else{
            dfs(idx-n, x, n, dp);
            dp[idx]+=dp[idx-n];
        }
    }
}

 

내 풀이(정답 - 2023.12.13)

import java.util.Arrays;

class Solution {
    private static final int OUT_OF_REACH = 1_000_001;
    
    public int solution(int x, int y, int n) {
        int[] dp = new int[y+1];
        Arrays.fill(dp, OUT_OF_REACH);
        dp[y]=0;
        
        for(int i=y; i>=0; i--){
            if(i%2==0&&i/2>=x){
                dp[i/2] = Math.min(dp[i/2], dp[i]+1);
            }
            if(i%3==0&&i/3>=x){
                dp[i/3] = Math.min(dp[i/3], dp[i]+1);
            }
            if(i-n>=x){
                dp[i-n] = Math.min(dp[i-n], dp[i]+1);
            }
        }
        
        return dp[x]==OUT_OF_REACH? -1 : dp[x];
    }
}

for문의 증감연산자를 i-=n에서 i--로 변경한 후 Integer.MAX_VALUE를 채우는 것에서 1,000,000을 채우도록 변경

Integer.MAX_VALUE를 채울 경우 dp[i]+1할 때 int overflow가 발생함에 따라 min메서드 호출 시 오버플로우된 값이 dp배열에 들어가게 된다.