프로그래머스 154538 숫자 변환하기 (DP)

 

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

프로그래머스

 

1. y+1만큼의 크기를 가진 배열에 해당 인덱스에 변환할 수 있는 최소 값을 넣어주면서 y까지 구하는 최소 연산 횟수를 구하면 된다.

2. 탐색 시작 인덱스는 x

- 만약 인덱스가 x가 아닌데, "dp 배열 값이 0" 일 때 그 값에 도달할 수 있는 방법이 없다는 뜻이므로 -1 을 넣고 포문 연산 continue.

 

import java.util.*;

class Solution {
    public int solution(int x, int y, int n) {
      int answer =0;
        int[] dp = new int [y+1];
         for(int i=x;i<y+1;i++){
            if(i!=x && dp[i]==0) {
                dp[i] = -1;
                continue;
            }
            if(i*3<=y){

                dp[i*3] = dp[i*3] ==0? dp[i]+1 : Math.min(dp[i]+1,dp[i*3]);
            }
            if(i*2<=y){
                dp[i*2] = dp[i*2] ==0? dp[i]+1: Math.min(dp[i]+1,dp[i*2]);
            }
            if(i+n <=y){
                dp[i+n] = dp[i+n] ==0? dp[i]+1 : Math.min(dp[i]+1, dp[i+n]);
            }
        }
    
        return dp[y];
    }
}