[154538] 숫자 변환하기

✔ 숫자 변환하기

[프로그래머스 154538]

문제 분석하기

3가지 경우에 대해 다이나믹 프로그래밍을 구현

손으로 풀어보기

1. 점화식의 형태와 의미를 도출
   • D[i]는 x를 i로 변환하기 위한 최소 연산 횟수
2. 점화식을 구함
   • D[x] = 0
   • D[i + n] = Math.min(D[i + n], D[i] + 1) 
   • D[i * 2] = Math.min(D[i * 2], D[i] + 1)
   • D[i * 3] = Math.min(D[i * 3], D[i] + 1)
   • 이때 D[i]가 y + 1이라면 변환할 수 없는 값이므로 D[i] = -1
3. 점화식으로 D 배열을 채운 후 D[y]의 값을 출력

슈도코드 작성하기

x, y, n(자연수)
D[y + 1](x를 i로 변환하기 위한 최소 연산 횟수)
D 배열을 y + 1로 모두 갱신
D[x] = 0
for(i -> x부터 y까지) {
    if(D[i]가 y + 1이라면) {
        변환할 수 없는 값이므로 D[i] = -1
        continue
    }
    if(i + n <= y) {
        D[i + n]을 Math.min(D[i + n], D[i] + 1)로 갱신
    }
    if(i * 2 <= y) {
        D[i * 2]를 Math.min(D[i * 2], D[i] + 1)로 갱신
    }
    if(i * 3 <= y) {
        D[i * 3]을 Math.min(D[i * 3], D[i] + 1)로 갱신
    }
}
D[y] 반환

코드 구현하기

/**
 * 154538) 숫자_변환하기
 */
public class L094_154538 {
    // x, y, n(자연수)
    public int solution(int x, int y, int n) {
        // D(x를 i로 변환하기 위한 최소 연산 횟수)
        int[] D = new int[y + 1];
        // D 배열을 y + 1로 모두 갱신
        Arrays.fill(D, y + 1);
        // x를 x로 변환하기 위한 최소 연산 횟수인 0으로 갱신
        D[x] = 0;
        for (int i = x; i <= y; i++) {
            // D[i]가 y + 1이라면
            if (D[i] == y + 1) {
                // 변환할 수 없는 값이므로 D[i] = -1
                D[i] = -1;
                continue;
            }
            if (i + n <= y)
                // D[i + n]을 Math.min(D[i + n], D[i] + 1)로 갱신
                D[i + n] = Math.min(D[i + n], D[i] + 1);
            if (i * 2 <= y)
                // D[i * 2]를 Math.min(D[i * 2], D[i] + 1)로 갱신
                D[i * 2] = Math.min(D[i * 2], D[i] + 1);
            if (i * 3 <= y)
                // D[i * 3]을 Math.min(D[i * 3], D[i] + 1)로 갱신
                D[i * 3] = Math.min(D[i * 3], D[i] + 1);
        }
        // D[y] 반환
        return D[y];
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L094_154538 solution = new L094_154538();

        int x = 10;
        int y = 40;
        int n = 5;

        int result = solution.solution(x, y, n);

        System.out.println(result);
    }
}