문제링크

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

구현방법

처음에 그리디 방식으로 진행하다가 값이 진행이 되지않아서 다른 분의 코드를 참조를해서 진행했습니다.

그리디 방식이 아닌 DP방식의 문제였습니다.

참조한 블로그의 구현방법:

x보다 큰값의 값을 y까지 진행하여서

2로 나눠지면서 나머지가 0 인경우 값이 x보다 큰경우 만 체크하고

3으로도 같은 방법을 진행하고

빼는 값도 같은 방법으로 진행합니다

그리고 그 값중 가장 작은 값을 뽑아내어서 MAX 보다 작은경우에는 만들수 있다는 것을 의미하므로 그 idx에 가장 작은값에 +1 을해서 dp 배열에 넣어줍니다.

y까지 진행이 끝나고 dp[y]의 값이 MAX 일경우에는 만들 수 없다는 것을 의미하기 때문에 -1을 리턴하고

아닌경우 dp[y] 값을 answer에 넣어서 리턴해줍니다.

참조 블로그 : https://ksb-dev.tistory.com/267

---

나중에 다시한번 풀어봐야할 것 같다.

구현알고리즘

• DP

CODE

import java.util.Arrays;
class Solution {
    int MAX =Integer.MAX_VALUE;
    public int solution(int x, int y, int n) {
        int answer = 0;

        int dp[] = new int[y+1];
        Arrays.fill(dp,0);
        for(int idx = x+1;idx <=y;idx++){
            int div2 = MAX;
            int div3 = MAX;
            int minus = MAX;
            
            int checking;
            //나눠지는경우 그 배열의 값을 가져옴
            if((idx /2 >= x) && (idx %2 == 0)){
                div2 = dp[idx/2];
            }
            //위의 방법과 같음
            if((idx/3 >= x) && (idx %3 ==0)){
                div3 = dp[idx/3];
            }
            //위의 방법과 같다.
            if(idx- n >= x){
                minus = dp[idx-n];
            }
            
            //각 계산 값중 최소값을 찾는다.
            checking = Math.min(div2,Math.min(div3,minus));
            
            //MAX값보다 작은경우 
            if(checking < MAX){
                dp[idx] = checking+1;
            }else{
                dp[idx] = MAX;
            }
        }
        if(dp[y] < MAX){
            answer = dp[y];
        }else
            answer = -1;

        return answer;
    }
}