숫자 변환하기

2026.05.06

문제 설명

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

• x에 n을 더합니다
• x에 2를 곱합니다.
• x에 3을 곱합니다.
  자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

제한사항

• 1 ≤ x ≤ y ≤ 1,000,000
• 1 ≤ n < y

입출력 예

문제 풀이

1차 실행 오류

---

메모리 초과
동일한 숫자가 큐에 삽입되는 것이 원인

---

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public int solution(int x, int y, int n) {
        int answer = 0;
        Deque<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{x, 0});
        
        while(!queue.isEmpty()) {
            int[] cur = queue.poll();
            int X = cur[0], count = cur[1];
            
            if (X == y) {
                return count;
            }
            if (X * 2 <= y) {
                queue.add(new int[]{X * 2, count + 1});
            }
            if (X * 3 <= y) {
                queue.add(new int[]{X * 3, count + 1});
            }
            if (X + n <= y) {
                queue.add(new int[]{X + n, count + 1});
            }
            
        }
        
        return -1;
    }
}

나의 코드

소요 시간: 1시간 7분

시간 복잡도: O($y$)

---

x *= 3을 먼저 하고 x > y가 될 때 x /= 3을 하고 x *= 2...
y / x도 해보며 이런저런 규칙을 찾아보려고 했지만,
규칙이 없었다.

claude AI에게 힌트를 요청했더니 BFS 방식으로 풀어야 한다고 알려주었다.

이를 통해 수학적인 규칙이 없는 문제들은
모든 조건을 탐색해야 한다는 깨달음을 얻었다.

이 문제의 경우 최소 조건을 알아내는 문제이므로
모든 조건을 탐색하는 DFS가 아닌,
최소 조건에 만족하면 바로 종료하는 BFS가 필요했다.

---

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public int solution(int x, int y, int n) {
        int answer = 0;
        Deque<int[]> queue = new ArrayDeque<>();
        boolean[] visited = new boolean[y + 1];
        queue.add(new int[]{x, 0});
        visited[x] = true;
        
        while(!queue.isEmpty()) {
            int[] cur = queue.poll();
            int X = cur[0], count = cur[1];
            
            if (X == y) {
                return count;
            }
            if (X * 2 <= y && !visited[X * 2]) {
                queue.add(new int[]{X * 2, count + 1});
                visited[X * 2] = true;
            }
            if (X * 3 <= y && !visited[X * 3]) {
                queue.add(new int[]{X * 3, count + 1});
                visited[X * 3] = true;
            }
            if (X + n <= y && !visited[X + n]) {
                queue.add(new int[]{X + n, count + 1});
                visited[X + n] = true;
            }
            
        }
        
        return -1;
    }
}

AI 코드

시간 복잡도: O($y$)

---

로직은 동일하나, forEach 문을 이용한 가독성을 증가시켰다.

---

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public int solution(int x, int y, int n) {
        if (x == y) return 0;
        
        boolean[] visited = new boolean[y + 1];
        Deque<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{x, 0});
        visited[x] = true;
        
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int X = cur[0], count = cur[1];
            
            for (int nx : new int[]{X * 2, X * 3, X + n}) {
                if (nx == y) return count + 1;
                if (nx < y && !visited[nx]) {
                    visited[nx] = true;
                    queue.add(new int[]{nx, count + 1});
                }
            }
        }
        
        return -1;
    }
}