Lv.2 : 숫자 변환하기

👉 문제링크

프로그래머스

---

---

🔸 문제 분석 🔸

• 정수 x, y, n이 입력된다.
• x를 3가지 연산 (+n, x2, x3) 으로 y를 만드는 최소 연산 횟수를 반환한다.
• y를만들 수 없으면 -1을 반환한다.

🔸 문제 풀이 🔸

• BFS와 DP로 풀이할 수 있다.
  • BFS는 각 인덱스를 처음 방문했으면 다음 3가지 연산을 수행해서 y를 찾아가는데, y를 초과하거나 이미 방문 했으면 제외한다.
  • DP는 x부터 y까지 인덱스를 늘려가며 계산하는데, 처음 방문이면 현재 값을 넣고 이미 값이 있으면 더 작은 값을 선택하는 방식으로 y를 만들어 간다.
• 아래 풀이는 DP방식을 선택했다.

---

🔸 코드 🔸

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

        for (int i = x + 1; i <= y; i++) {
            dp[i] = Integer.MAX_VALUE;
        }

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

            }
        }

        return dp[y] == Integer.MAX_VALUE ? -1 : dp[y];
    }
}

🔸 코드 해석 🔸

• int형 배열 dp의 인덱스 x+1 ~ y 을 Integer.MAX_VALUE 값으로 초기화한다.
• x부터 y-1까지 계산을 반복한다.
  • dp[i]가 Integer.MAX_VALUE면 방문하지 않은 인덱스이므로 제외한다.
  • 문제에서 주어진 3가지 연산을 수행한다.
    • 인덱스가 y를 넘지 않으면, 저장 된 값과 현재 값 중 최소값을 저장한다.
• dp[y]를 반환한다. 만약 방문하지 않았다면 -1을 반환한다.

---

 

🔸 end 🔸

• 처음에는 BFS로 풀이했는데, 시간초과가 나서 DP로 변경하고자 했다.
  • BFS로 풀이하면 안되는 문제인 줄 알았는데, 방문체크를 하지 않아서 메모리가 터져버린 탓이었다.
  • 코테를 하도 안풀었더니 자신 있었던 DFS, BFS문제를 초보적인 실수로 틀리게 되니 많이 반성하게 된다...
• DP로 풀이 할 때도 잘못 생각 한 부분이 있어서 오류를 찾는데 시간이 걸렸다.
  • 결론부터 말하자면 인덱스를 처음 방문했을때의 시도 횟수가 바로 최소값이 되는 줄 알고 그대로 저장해갔다.
  • BFS를 시도하다가 바꿔서 헷깔린 것 같다.
  • 최초로 dp[i]값을 변경했을때 보다 다른 연산을 통해 더 낮은 횟수로 도착할 수 있었다.