[baekjoon] 16953 A->B (Javascript, Python)

16953번: A → B (acmicpc.net)

16953번: A → B

---

알고리즘 : dfs

 

- Javascript

function solution() {
  let input = require("fs")
    .readFileSync("input.txt") //"/dev/stdin"
    .toString()
    .split("\n")
    .map((val) => val.trim());

  let [a, b] = input
    .shift()
    .split(" ")
    .map((v) => +v);

  // 2를 곱한다.
  // 1을 수의 가장 오른쪽에 추가한다.

  let ans;
  const dfs = (a, b, cnt) => {
    if (a === b) {
      ans = cnt;
      return;
    } else if (a > b) return;

    dfs(a * 2, b, cnt + 1);
    dfs(+[a, 1].join(""), b, cnt + 1);
  };

  dfs(a, b, 0);

  console.log(!ans ? -1 : ans + 1);
}

solution();

 

 

- Python

import sys

sys.stdin = open("baekjoon/16953/input.txt","r")
input = sys.stdin.readline().strip()

[a,b]=list(map(int,input.split(" ")))

# 제출용
# [a,b]=list(map(int,input().split(" ")))

ans=-1
def dfs(a,b,cnt):
    global ans
    if(a>b):
        return
    if(a==b):
        ans=cnt
        return
    
    dfs(a*2,b,cnt+1)
    dfs(int("".join(map(str,[a,1]))),b,cnt+1)

dfs(a,b,0)

print(-1 if ans==-1 else ans+1)