[프로그래머스 / Java] Lv.2 숫자 변환하기

Question

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

프로그래머스

---

Algorithm

1. dp 배열 정의
   • dp[i] = x에서 i로 변환하는 최소 연산 횟수
2. 초기 상태 설정
   • dp[x] = 0 (시작 숫자라서 연산 횟수 0)
   • 나머지는 아직 도달하지 않았으므로 0으로 초기화
3. x부터 y까지 순차적으로 탐색
   • 현재 위치 i가 시작점이 아니고 dp[i] == 0이면 → 도달 불가능하므로 -1 표시 후 건너뜀
   • 그렇지 않다면(즉, 도달 가능한 숫자라면) 다음 연산을 적용해본다.
4. 세 가지 연산 적용
   • i * 2 (y 이하일 때만)
   • i * 3 (y 이하일 때만)
   • i + n (y 이하일 때만)
5. 위 연산으로 도달 가능한 숫자 next에 대해
   • dp[next] = min(dp[next], dp[i] + 1)
   • 아직 도달하지 못했다면 dp[i] + 1 저장
   • 이미 값이 있다면 더 작은 값으로 갱신
6. 최종 결과 반환
   • dp[y] 값이 최소 연산 횟수
   • 만약 dp[y] == 0이라면 → 도달 불가능 → -1 반환

---

Code

class Solution {
    public int solution(int x, int y, int n) {
        // dp[i] = x에서 i로 가는 최소 연산 횟수
        int[] dp = new int[y + 1];

        // x부터 y까지 숫자를 차례로 확인하면서 dp를 채움
        for (int i = x; i < y + 1; i++) {
            // 시작점(x)이 아니고, 아직 도달 못한 숫자라면
            if (i != x && dp[i] == 0) {
                dp[i] = -1; // 도달 불가 표시
                continue;   // 이 숫자에서 확장은 못하니까 스킵
            }

            // 1) 현재 숫자 i에서 *2
            if (i * 2 <= y) {
                // 아직 안 채워진 곳이면 dp[i]+1 저장
                // 이미 값이 있으면 더 작은 값으로 갱신
                dp[i * 2] = (dp[i * 2] == 0) ? dp[i] + 1 : Math.min(dp[i] + 1, dp[i * 2]);
            }

            // 2) 현재 숫자 i에서 *3
            if (i * 3 <= y) {
                dp[i * 3] = (dp[i * 3] == 0) ? dp[i] + 1 : Math.min(dp[i] + 1, dp[i * 3]);
            }

            // 3) 현재 숫자 i에서 +n
            if (i + n <= y) {
                dp[i + n] = (dp[i + n] == 0) ? dp[i] + 1 : Math.min(dp[i] + 1, dp[i + n]);
            }
        }

        // 최종적으로 dp[y] = x에서 y까지 가는 최소 연산 횟수
        return dp[y];
    }
}

---

출처

https://sasca37.tistory.com/307#google_vignette

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