본문 바로가기
CS/알고리즘

[Javascript] 백준 16963: A -> B

by s0ojin 2023. 2. 2.

문제

정수 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

 


문제 풀이

1) B가 A가 되도록 루프를 돌면서 둘중 한가지를 수행할 때마다 count를 +1 해준다.

  • 현재의 B를 문자로 바꾸어 문자의 맨 뒤가 1이면(일의 자리가 1이면) 해당 문자를 지우고 B에 저장한다.
  • 일의 자리가 1이 아니면 2로 나눈다.


2) B가 정확히 A가 되면 루프를 멈추며 count를 출력해준다.

3) B가 A가 되지 못하고 루프가 끝나면 -1을 출력해준다.

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split(" ");

let A = Number(input[0]);
let B = Number(input[1]);

let count = 0;

while (true) {
  let StringB = String(B);

  if (StringB[StringB.length - 1] === "1") {
    StringB = StringB.substring(0, StringB.length - 1);
    B = Number(StringB);
    count++;
  } else {
    B = B / 2;
    count++;
  }

  if (B === A) {
    return console.log(count + 1);
  }

  if (B < 1) {
    return console.log(-1);
  }
}

 

 

 

댓글