[프로그래머스] 숫자 변환하기(JAVA)

문제

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

---

풀이(33분)

import java.util.*;

public class Solution {
    public static int[] arr;

    public int solution(int x, int y, int n) {
        arr = new int[y + 1];
        Arrays.fill(arr, Integer.MAX_VALUE);
        arr[y] = 0;

        for (int i = y; i >= x; i--) {
            if (arr[i] == Integer.MAX_VALUE) continue; // 초기화되지 않은 값은 스킵
            if (i % 2 == 0) arr[i / 2] = Math.min(arr[i / 2], arr[i] + 1);
            if (i % 3 == 0) arr[i / 3] = Math.min(arr[i / 3], arr[i] + 1);
            if (i - n >= x) arr[i - n] = Math.min(arr[i - n], arr[i] + 1);
        }

        return arr[x] == Integer.MAX_VALUE ? -1 : arr[x];
    }
}

 

초반에 중복되는 것을 생각하지 않고, dfs로 진행하였다.

하지만 이 경우 반복되는 것이 너무 많았고, % 6 == 0인 것을 먼저 진행한 후에 dfs로 하려고 하였다.

하지만 그렇게 하더라도 중복되거나 반복되는 검사가 너무 많았다.

 

따라서 문제의 값에서 내려오며 검사를 진행한 후에 값을 채워넣는 dp 방식을 이용하여 해결하였다.

 

추가적으로, for문에서 계산을 효율적으로 하기 위해 증감식 부분에 i -= n으로 하였는데, 이 경우 3개의 테스트 케이스에 틀림을 알 수있다.

이는 나누기 연산이 된 후에 증감문이 적용되는 것에 대한 오류가 발생할 수 있다는 것을 알게되었고, -- 로 진행하였다.