[PROGRAMMERS] 숫자 변환하기

해당 숫자까지 도달을 하기 위해서 최소한의 연산으로 얼마만에 가는지를 구하는 것이 문제이다.

 

dp를 이용해서 최소한의 움직임을 계산하기 위해서 Math.min 함수를 사용해서 얼마 안 움직인 것을 캐치하고, y 값 위치 전까지 카운팅을 진행하는 코드이다.

 

import java.util.*;
class Solution {
    public int solution(int x, int y, int n) {
        
        int answer = 0;
        
        int dp[] = new int[1_000_001];
        
        Arrays.fill(dp, -1);
        
        dp[x] = 0;
        
        for(int i = x; i <= y; i++){
            
            if(dp[i] != -1){
                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);
                    }
                }
            }
        }
        answer = dp[y];
        return answer;
    }
}