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

승래·2026년 4월 3일

프로그래머스 Lv.2 - 숫자 변환하기

요구사항

x에서 시작해서 y로 만들 수 있는 최소 연산 횟수를 구하는 문제
가능한 연산: n 더하기, 2 곱하기, 3 곱하기
불가능하면 -1 반환

접근 방식

BFS와 DP 두 가지 방식으로 풀었다.

풀이 1 - BFS

x부터 시작해서 +n, 2, 3 연산으로 y에 도달하는 최소 횟수
핵심: visit 배열로 이미 방문한 노드 체크
→ visit 없으면 같은 노드를 무한히 방문해서 시간초과!
→ visit 있으면 각 노드를 최대 한 번만 방문 → O(y)

풀이 2 - DP

dp[i] = x에서 i로 가는 최소 연산 횟수
순방향으로 갱신:
dp[i+n] = min(dp[i+n], dp[i] + 1)
dp[i2] = min(dp[i2], dp[i] + 1)
dp[i3] = min(dp[i3], dp[i] + 1)

역방향 DP가 어려운 이유

dp[i] = min(dp[i-n], dp[i/2], dp[i/3]) 로 구현하면
→ i가 n으로 나누어지지 않거나 2, 3으로 나누어지지 않는 경우 처리 복잡
→ 도달 불가능(-1) 케이스 처리도 어려움
순방향이 훨씬 자연스럽고 구현이 쉬움!

복잡도

O(y) = O(1,000,000) → 충분히 가능
1억번 연산 ≈ 1초 기준으로
O(n) = 100만번 → 가능 ✅
O(n²) = 1조번 → 시간초과 ❌

코드 - BFS

import java.util.*;

class Point {
    int now, cnt;
    public Point(int now, int cnt) {
        this.now = now; this.cnt = cnt;
    }
}

class Solution {
    public int solution(int x, int y, int n) {
        return bfs(x, y, n);
    }

    public int bfs(int x, int y, int n) {
        Queue<Point> q = new LinkedList<>();
        q.offer(new Point(x, 0));
        boolean[] visit = new boolean[y+1];
        visit[x] = true;

        while (!q.isEmpty()) {
            Point p = q.poll();
            if (p.now == y) return p.cnt;

            int[] next = {p.now + n, p.now * 2, p.now * 3};
            for (int cal : next) {
                if (cal > y || visit[cal]) continue;
                visit[cal] = true;
                q.offer(new Point(cal, p.cnt + 1));
            }
        }
        return -1;
    }
}

코드 - DP

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; i++) {
            if (dp[i] == Integer.MAX_VALUE) continue; // 도달 불가능한 노드 skip
            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];
    }
}