백준 16953: A =>B - javascript(그리디)

문제 출처 

https://www.acmicpc.net/problem/16953

16953번: A → B

문제

정수 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) A 를 B로 바꾸라고? 

=> 그럼 B에서 A를 바꾸는 방법을 생각해봐야겠다 ! 

 

정답 풀이 코드 

let input = require('fs').readFileSync('/dev/stdin').toString().split('\n');
const [A,B] = input.shift().split(' ').map(Number);
function solution(A,B){
let cnt = 1;
while(1){
   if(String(B).split('').pop() === '1'){
       let len = String(B).length;
       B = Number(String(B).slice(0, len-1));
   }else{
       B = Number(B)/2;
   }
    cnt++;
    if(B === A){
        return cnt;
    }
    if(B < A) return -1
  }
}
const answer = solution(A,B)
console.log(answer);

의사 코드 추가

let input = require('fs').readFileSync('/dev/stdin').toString().split('\n');
const [A,B] = input.shift().split(' ').map(Number);
function solution(A,B){
let cnt = 1;
while(1){
   if(String(B).split('').pop() === '1'){ //B의 끝자리가 1일때
       let len = String(B).length;
       B = Number(String(B).slice(0, len-1)); //1을 없앤다
   }else{ //B의 끝자리가 1이 아닐 때
       B = Number(B)/2;  //2를 나눈다. 
   }
    cnt++;
    if(B === A){ //같으면 cnt 출력
        return cnt;
    }
    if(B < A) return -1 //B가 A보다 작으면 -1출력 
  }
}
const answer = solution(A,B)
console.log(answer);