숫자 변환하기(프로그래머스-연습문제)

문제

코드

class Solution {
    static final int MAX=Integer.MAX_VALUE;
    public int solution(int x, int y, int n) {
        int answer=0;
        int[] dp=new int[y+1];
        for(int i=x+1;i<=y;i++){
            int a=MAX, b=MAX, c=MAX,min;
            if(i-n>=x) a=dp[i-n];
            if(i%2==0&&i/2>=x) b=dp[i/2];
            if(i%3==0&&i/3>=x) c=dp[i/3];
            min=Math.min(a,b);
            min=Math.min(min,c);
            dp[i]=(min!=MAX)?min+1:MAX;
        }
        return (dp[y]==MAX) ? -1:dp[y];
    }
   
}

풀이

(1) y+1 크기의 배열을 만든다. ex) dp[40]에는 40을 만들 수 있는 최소 횟수가 들어간다.
(2) x+1부터 y번째 인덱스까지 반복해서 dp과정을 반복한다.

• dp[i]에는 dp[i-n],dp[i/2],dp[i/3]중 가장 작은 값+1 이 들어간다.
• 만약 dp[i-n],dp[i/2],dp[i/3]이 없다면, dp[i]에는 Integer.MAX_VALUE가 들어간다.
• Integer.MAX_VALUE값이 들어간 곳은 그 수를 만들 수 있는 방법이 없다는 뜻이다.

(3)dp[y] 값이 결과가 된다.

결과

처음에는 다이나믹 프로그래밍 문제인줄 몰랐다. dfs로도 해보고, 그리디로도 해봤는데 모두 아니어서, 다른 사람 코드를 참고했다.
dp문제가 너무 오랜만이다 보니 생각이 나지 않았고, dp문제라는 걸 알았음에도 푸는데 많이 버벅였다. 아직도 많이 부족한 것 같다. 더 노력해야 한다.
출처 : 프로그래머스 코딩 테스트 연습 https://school.programmers.co.kr/learn/challenges