✅ 문제

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

x에 n을 더합니다
x에 2를 곱합니다.
x에 3을 곱합니다.

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

✅ 풀이

첫 번째 접근방식 (DFS)

모든 경우의 수를 DFS로 탐색하면서 nx === y 일 때 answer에 담아준 뒤 최솟값을 출력해주었다. 결과는 반만 맞았다. 런타임 에러는 왜 발생하는지 정확하게는 모르겠지만.. 추측건데 재귀로 인한 스택 오버 플로우 문제인 것 같다.

점수 50 / 100
테스트 케이스
- 5, 9, 10, 11, 14 (런타임 에러)
- 15, 16 (시간 초과)

function solution(x, y, n) {
  let answer = [];
  
  const dfs = (nx, depth = 0) => {
    if (nx >= y) {
      if (nx === y) {
        answer.push(depth);
      }
      
      return;
    }
    
    dfs(nx * 3, depth + 1);
    dfs(nx * 2, depth + 1);
    dfs(nx + n, depth + 1);
  }
  
  dfs(x);
  
  return answer.length > 0 ? Math.min(...answer) : -1;
}

두 번째 접근 방식 (BFS)

더 나은 시간복잡도를 위해 BFS를 사용하여 탐색이 가능한 경우로만 탐색해주는 방식으로 풀이했다. 런타임 에러는 발생하지 않았고, 5개의 테스트 케이스만 시간 초과로 실패했다. 여기서 시간을 더 줄일 수 있는 방법이 뭐가 있을까 1시간 넘게 생각하다가 결국 다른 사람들의 풀이에서 도움을 얻었다.

점수 68.8 / 100
테스트 케이스
- 5, 7, 9, 10, 11 (시간 초과)

function solution(x, y, n) {
  const bfs = (sx) => {
    const queue = [[sx, 0]];
    
    while (queue.length) {
      const [sx, sd] = queue.shift();
      
      if (sx === y) {
        return [sx, sd];        
      }
      
      if (sx * 3 <= y) {
        queue.push([sx * 3, sd + 1]);
      }
      
      if (sx * 2 <= y) {
        queue.push([sx * 2, sd + 1]);
      }
      
      if (sx + n <= y) {
        queue.push([sx + n, sd + 1]);
      }
    }
    
  }
  
  const answer = bfs(x);
  
  return answer ? answer[1] : -1;
}

세 번째 접근 방식 (BFS + y를 기준으로 역순회) (통과)

문제를 처음 풀이했을 때 y를 기준으로 각 1,2,3 각 조건들을 반대로 수행하며 x를 만들어나갔었는데, 그 방식을 BFS와 함께 사용하면 충분히 시간을 단축시킬 수 있다.

function solution(x, y, n) {
  const bfs = (sy) => {
    const queue = [[sy, 0]];
    
    while (queue.length) {
      const [ny, nd] = queue.shift();
      
      if (ny === x) {
        return [ny, nd];        
      }
      
      if (ny % 3 === 0) {
        queue.push([ny / 3, nd + 1]);
      }
      
      if (ny % 2 === 0) {
        queue.push([ny / 2, nd + 1]);
      }
      
      if (ny - n >= x) {
        queue.push([ny - n, nd + 1]);
      }
    }
    
  }
  
  const answer = bfs(y);
  
  return answer ? answer[1] : -1;
}

시간복잡도를 개선하는 것이 쉽지 않다는 것을 다시 한 번 느꼈다. 한 번에 여러 방향을 보기가 힘들지만, 연습하는 것 밖에 답이 없을 것 같다. 정진하자.