숫자 변환하기

문제

풀이

import java.util.*;
// DP 문제
// 1.일단 DP[] 테이블생성 후 초기 값 대입.
// 2.점화식을 찾는다.

class Solution {
    public int solution(int x, int y, int n) {
        int answer = 0;
        int[] dp = new int[y+1];
        
        for(int i=0; i<dp.length; 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가 생각났는데, 문제 입력값 조건 보고 바로 안될거같아서 DP문제라는걸 깨달음.

바로 DP[] 생성해주고 DP[]에 최소 연산의 수를 저장해준다. 이때 최소연산의 수를 비교하기 때문에 초기값은 MAX값으로 셋팅.

for문으로 x~y까지 돌려주고 해당 3가지 경우의 수에서 없는 수는 MAX값일거니깐 다 continue; 시켜주면된다.