A -> B

문제

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

• 2를 곱한다.
• 1을 수의 가장 오른쪽에 추가한다.
  A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 10^9)가 주어진다.

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

예제 입력1

2 162

예제 출력1

5

예제 입력2

4 42

예제 출력2

-1

예제 입력3

100 40021

예제 출력3

5

풀이

const fs = require("fs");
const path = require("path");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : path.join(__dirname, "input.txt"))
  .toString()
  .trim()
  .split("\n");

const solution = (input) => {
  const [A, B] = input[0].split(" ").map(Number);
  const limit = 1000000000;

  const bfs = () => {
    let queue = [[A, 1]];
    let head = 0;

    while (head < queue.length) {
      const [cur, cnt] = queue[head++];

      if (cur === B) return cnt;

      let next = [cur * 2, parseInt(cur.toString() + "1")];
      for (let i = 0; i < 2; i++) {
        if (next[i] <= limit) {
          queue.push([next[i], cnt + 1]);
        }
      }
    }
    return -1;
  };

  console.log(bfs());
};

solution(input);

💡 아이디어 / 접근법

1. 이거 그냥 숨바꼭질에서 계산 방법만 바뀐 거임
2. 계산이 -1, +1, *2 가 아니라 *2 혹은 오른쪽에 1 붙이기로 바뀜
3. 따라서 visited 자체도 필요 없음 왜 why? 어차피 짝수로 증가하기 때문에 오른쪽 끝에 1이 올 일이 없기 때문
4. 그렇게 해당값이 되면 cnt 리턴 못하면 -1 리턴

🤔 후기

저번에 풀었던 숨바꼭질 문제에서 다음 좌표로 넘어가는 조건만 바꾸면 거의 동일한 문제!