[java] 프로그래머스스쿨 연습문제 Lv.2 DP 문제 모음

2. 숫자 변환하기

코딩테스트 연습 - 숫자 변환하기 | 프로그래머스 스쿨 (programmers.co.kr)

풀이

1. 동적 계획법(Dynamic Programming) 아이디어를 활용한다. 2. 정수형 배열 dp를 크기 y+1로 선언한 후, 가능한 가장 큰 값(Integer.MAX_VALUE)으로 채운다. 3-1. 각 인덱스를 '만들 수 있는 값'으로 생각한다. 3-2. 각 인덱스 값을 만들기 위해 필요한 연산 횟수를 저장한다 3-3. 그러니까 """dp[ i ] 의 값은 곧 x가 i로 변환되기 위한 연산 횟수""" 인 것임 3-4. 이 과정은 memoization을 위한 것 4. 배열에 만들 수 있는 값을 인덱스로 삼아 최소 연산 횟수를 저장한다 4-1. for문으로 x부터 시작해 y까지 4-2. 만약 dp[i]값이 Integer.MAX_VALUE면, i를 만들 수 있는 방법이 없는 것이므로 continue 5. dp[y]의 값이 Integer.MAX_VALUE라면 -1을, 아니라면 dp[y]의 값을 반환

회고

- 나 자바에서 동적계획법 썼다

코드 (접은 글)

import java.util.*;

class Solution {
    public int solution(int x, int y, int n) {
        int[] dp = new int[y + 1];

        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[x] = 0;

        for (int i = x; i < y + 1; i++) {
            if (dp[i] == Integer.MAX_VALUE)
                continue;
            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 (i + n <= y)
                dp[i + n] = Math.min(dp[i + n], dp[i] + 1);
        }
        if (dp[y] == Integer.MAX_VALUE)
            return -1;
        return dp[y];
    }
}