문제

시간 제한 	메모리 제한	 제출 	정답     맞힌 사람  정답 비율
2 초	        512 MB	    31537	13143	10529	40.192%

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

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

입력
첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

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

예제 입력 1

2 162

예제 출력 1

5

2 → 4 → 8 → 81 → 162

예제 입력 2

4 42

예제 출력 2

-1

예제 입력 3

100 40021

예제 출력 3

5

100 → 200 → 2001 → 4002 → 40021

나의 코드

let input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split(" ");
const [A, B] = input.map(Number);
let ans = 0;
function solution(A, B, count = 0) {
  if (A <= B) {
    count++;
    if (!isNaN(solution(2 * A, B, count))) ans += solution(2 * A, B, count);
    if (!isNaN(solution(Number(String(A) + "1"), B, count)))
      ans += solution(Number(String(A) + "1"), B, count);
  }
  if (A === B) return count;
}
solution(A, B);
console.log(ans ? ans : -1);

이진 트리를 생각하면서 코드를 짰다.
각 step에서 A에 2를 곱해주는 것과 A 뒤에 "1"를 더해주는 것을 자식 노드로 놓는 것을 머릿속에 그려보고 시작했다.
A가 B보다 커지면 A와 B를 비교하여 같을 경우에만 count를 return 하는 것이다.
물론 아무리 step을 거쳐도 A가 B가 될 수 없는 경우에는 ans = 0이 되므로 이 때는 -1을 return 한다.

---

미래에서 왔음둥~
오늘은 2023년 8월 11일!
오늘도 파이썬으로 복습하기!

from sys import stdin as s

s = open("input.txt", "rt")  # 주석 처리해야 하는 부분

a, b = map(int, s.readline().split())

count = 1

while b > a:
    if b % 10 == 1:
        b //= 10
    else:
        b /= 2
    count += 1

print(count if a == b else -1)

자바스크립트로 풀 때 A에서 B로 가는 풀이로 접근했군.
그럴 필요가 없다~!
B에서 A로 가면 아주 간단히 해결 가능~
B를 10으로 나눈 나머지가 1이면 10으로 나눈 몫을 B에 재할당하고
그 외에는 2로 나눠주면 된다.

코드도 깔끔해졌군.
그럼 안녕~!