백준 16953번 JavaScript

백준 16953번

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

let [a, b] = input[0].split(' ').map(Number);
let count = 0;

//b가 a와 같아지거나 작아지기 전까지 반복
while(a <= b){
  //끝자리가 1인 경우는 끝자리에 1을 추가했을 경우
  if(b%10===1){
    b = Number.parseInt(b/10);
  //이외에는 2를 곱한 경우이므로 다시 나눠준다
  }else b /= 2;
  count += 1;
  if (a===b) {
    console.log(count +1);
    break;
  }
}
//a를 b로 바꿀 수 없을 경우
if(a!==b) console.log(-1);

문제를 뒤집어서 생각했습니다. A에서 B가 된다는 것은 계산했던 연산이 정해져 있다는 것입니다.
연산 후 1의자리가 1이라면 마지막 연산은 2를 곱했던 것은 아닙니다.
a에서 b가 되고자 할때 할 연산들을 되감기했을 때 a와 b가 일치하지 않는다면, a가 b가 될 수 없는 경우입니다.
매 상황에서 이동 경로는 단 하나만 존재하므로, 그리디 알고리즘에 해당한다고 볼 수 있습니다.